[PE] - Project Euler club

[Dason]

Hola,

I've been wanting to do this for a while but I think it would be fun to get a group together to work on Project Euler problems.

I have a personal account there but I was doing those mainly to help get more acquainted with Python. What I really want to do is to find nice ways to do these problems using R. If you're interested in honing your math/R skills I welcome you to join. I created an account for the forum

User Name: talkstats

I'm not sure I want to post the password directly here but if you're interested either send me a PM or just make a post and I'll give you the password and you can try some problems out. To give you a taste of what Project Euler is (for those that don't know) you solve problems like this:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

so you could write a quick R program to answer this pretty easily. I'll put the answer and 3 different ways to achieve the result in R in a spoiler:

Spoiler

The answer is: 233168

# TODO: Add comment
# 
# Author: dasonk
###############################################################################


# Problem 1:
# If we list all the natural numbers below 10 that are 
# multiples of 3 or 5, we get 3, 5, 6 and 9. 
# The sum of these multiples is 23.
#
# Find the sum of all the multiples of 3 or 5 below 1000.

# One way
n <- 999
nums <- 1:n
idx1 <- seq(3, n, 3)
idx2 <- seq(5, n, 5)
idx <- unique(c(idx1,idx2))
sum(nums[idx])

# Another way
idx <- c(F,F,T,F,T,T,F,F,T,T,F,T,F,F,T)
sum(nums[idx])

## Third way
sum(which(nums %% 3 == 0 | nums %% 5 == 0))

This is a relatively simple problem and probably wouldn't require much collaboration to solve. I still think it would be interested to see a couple different ways to achieve the same goal within R for these simple problems. However, the problems get quite a bit more difficult and require much more creative math/programming skills to achieve and answer in a reasonable amount of time. Some problems have me stumped and I think it would be nice to have a place to discuss ideas.

An example of a more difficult problem:

For two positive integers a and b, the Ulam sequence U(a,b) is defined by U(a,b)1 = a, U(a,b)2 = b and for k > 2, U(a,b)k is the smallest integer greater than U(a,b)(k-1) which can be written in exactly one way as the sum of two distinct previous members of U(a,b).

For example, the sequence U(1,2) begins with
1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
5 does not belong to it because 5 = 1 + 4 = 2 + 3 has two representations as the sum of two previous members, likewise 7 = 1 + 6 = 3 + 4.

Find U(2,2n+1)k for 2 n 10, where k = 1011.

So would anybody be interested in tackling these with me?

 

[bryangoodrich]

I'm interested as long as I find time. My first thought and correct solution was your 3rd way on that first problem. The vectorization in R made it very easy to perceive that solution: subset the vector of integers in [1, 999] by whether they are multiples of 3 or 5 by using which and the modulus condition. Obviously, wrap that in a sum and you have the answer in one line.

 

[Dason]

I'm interested as long as I find time. My first thought and correct solution was your 3rd way on that first problem. The vectorization in R made it very easy to perceive that solution: subset the vector of integers in [1, 999] by whether they are multiples of 3 or 5 by using which and the modulus condition. Obviously, wrap that in a sum and you have the answer in one line.

Indeed. I find the third way the most natural and it's what I thought of initially but I wanted to post some other longer options to show a nice progression of ways to do it. And like I said that is the first problem and is essentially there to get the user comfortable with submitting an answer.

 

[Jake]

It sounds like fun. Although like bryan I worry a little about time. Specifically, my worry is that I'll become wrapped up in trying to solve these problems for hours on end and ignore my actual work! But I guess count me in and I'll try to control myself...

 

[Dason]

I sent the password to both of you through private messages.

I also did... 2 more problems I think and I'll get my code posted for that tomorrow when I'm back at my office computer.

 

[Dason]

Problem 53:
(I'm too lazy to convert this to a nice format for the forum so it looks pretty crappy):
There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345​

In combinatorics, we use the notation, 5C3 = 10.
In general,

nCr =

n!
r!(n

r)!​

,where r

n, n! = n

(n

1)

...

3

2

1, and 0! = 1.​

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many, not necessarily distinct, values of nCr, for 1

n

100, are greater than one-million?

Spoiler

My code definitely gets the answer and does so pretty quickly but I feel there should be a nicer way to do it. You can't just stick 1:100 into the "get" function I write though so this was the best I could come up with (off the top of my head) without writing an explicit loop.

get <- function(x){return(sum(choose(x, 0:x) > 1000000))}
sum(apply(matrix(1:100, ncol = 1), 1, get))

#Answer: 4075

 

[Dason]

And it looks like somebody did problem 2 without posting their code...

 

[Dason]

Problem 48:
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

Spoiler

I tried to add some comments to the code. I'd like to see a better way to do this one. Not because I think it can't be done - but because I'm actually interested in it. 1000^1000 will cause R to spit back Inf which is why we need the powmod function here. It could clearly be made more general to return a^b %% c instead but since we don't need that functionality for this problem I didn't code that in.

# x %% mod will give the last 10 digits of x
mod <- 10000000000

# Computes x^x %% mod with little chance of an overflow
powmod <- function(base, mod){
    ans <- base
    for(i in 2:base){
        ans <- (base*ans) %% mod
    }
    return(ans)
}

# preallocate our answer vector
j <- numeric(1000)
# powmod wouldn't work well for base = 1
j[1] <- 1
# Get x^x %% mod for 2 to 1000
for(i in 2:1000){
    j[i] <- powmod(i, mod)
}

# Answer
sum(j) %% mod

 

[spunky]

Problem 48:
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

i will h8 you forever for this problem... as soon as i saw it i couldn't resist... now i'm behind on my thesis work and stoopid R spew an unholy "Inf" at me... my TI-89 crashed trying to do it... i wonder if Maple can crack it just with brute computational force...

 

[Dason]

Calculating 1^1 + 2^2 + ... + 1000^1000 and then figuring out the last ten digits is definitely not the way to go on that problem if you want to use R.

Mathematica/WolframAlpha on the other hand handles it just fine...

 

[spunky]

Mathematica/WolframAlpha on the other hand handles it just fine...

that's exaaactly what i was thinking... although i dunno why i was only taught to work on Maple and not Mathematica... however i'm pretty sure they can both do the same things rather well...


ps- i think it may have to do with the fact that Maple is a Canadian company so the uni wanted to keep it local...

 

[Dason]

I used Maple a little bit in undergrad but we mainly used Mathematica. But I haven't really touched Mathematica since I started grad school. Wolfram Alpha is nice though and I pull it up every now and then for just random things.

Wolfram Alpha has answer to some important questions.

 

[spunky]

Wolfram Alpha has answer to some important questions.

oohhh--myyy---FFFFFFFFiiiing GOD!!! Wolfram Alpha also has an answer to the "ultimate question... the answer to life the universe and everything"!!!!!!! people, go look for it! (unless you didnt watch hitchhiker's guide to the galaxy, in which case you'll totally miss the point...)

you're right Dason, Wolfram Alpha *DOES* have the answer to some important questions...

 

[Dason]

Spunky and I discussed question 25 a little bit over PM which got me interested in it. My suggestion to spunky for an analytic way to do this problem gets close to the answer but is off slightly so I coded something up quick to figure it out.

Problem 25:
The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn

1 + Fn

2, where F1 = 1 and F2 = 1.​

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144​

The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?

Spoiler

Note: I figured out what I did wrong in the following paragraph and I explain it briefly at the end of the post.

Analytically I was able to get pretty close to the solution. Fn can be written as the closest integer to \(\frac{\phi^n}{\sqrt{5}}\) where \(\phi = \frac{1 + \sqrt{5}}{2}\) so using some logs if we drop the "closest integer" part of this we get that the n of interest is approximately \(\frac{1000 + \log(\sqrt{5})}{\log(\phi)} = 4786.644\) ; Note that I was using log base 10 here because we're interested in the number of digits in the number. So I tried 4786 and 4787 but neither worked. I knew it would have to be in that general area but I wanted to get the answer without just randomly guessing in that area. I could use the exact formula for Fn that doesn't use the closest integer function but that isn't quite as nice to work with analytically. Coding up the answer isn't that bad but you need to deal with numbers that have at least 1000 digits.

The code could be quite a bit better but I just threw this together quick. I know there are better ways to deal with really large numbers in R but I felt like coding up my own way by using vectors.

# Want want to go to n = 1000 digits
n <- 1000
# preallocate these vectors
x1 <- numeric(n)
x2 <- numeric(n)
# Starting values for fibonacci
x1[1] <- 1
x2[1] <- 1
# x2 is currently the second fibonacci number
count <- 2

# Assume we just added two vectors that were in
# reduced form - we'll only ever need to carry
# 1 to the next spot.
reduce <- function(x){
    n <- max(which(x != 0))
    for(i in 1:n){
        if(x[i] >= 10){
            x[i+1] <- x[i+1] + 1
            x[i] <- x[i] %% 10
        }
    }
    return(x)
}

while(x2[1000] == 0){
    x3 <- x2
    x2 <- reduce(x2 + x1)
    x1 <- x3
    count <- count + 1
}

# Answer
count

# answer: 4782

Edit: After all of that I figured out why my analytic solution didn't work. I didn't want to solve for 1000 = log10(phi^n/sqrt(5)). We wanted to solve for 999 = log10(phi^n/sqrt(5)). Silly me...

 

[Jake]

And it looks like somebody did problem 2 without posting their code...

That was me. Sorry.

The problem was:

"Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms."

Spoiler

fibMax <- function(max){
  current <- 1:2
  evenSum <- 2
  nextFib <- sum(current)
  while (nextFib <= max){
    evenSum <- evenSum + nextFib*(!nextFib %% 2)
    current <- c(current[2], nextFib)
    nextFib <- sum(current)
  }
  return(evenSum)
}

############################

> fibMax(4000000)
[1] 4613732

After submitting the answer and looking at the suggested solution methods, I got a bit of a sense of what PE is looking for. My solution was pretty much the obvious one but there were some more elegant ways to go about it. In looking over some of the other problems I can see that this is the case for many of them--there is a fairly obvious solution but probably also some more elegant and less obvious solutions. In the future I'll have to think harder about finding those.

 

[Dason]

That's one of the reasons I kind of wanted to start this thread. There are very elegant ways to solve these problems and there are very ugly ways to solve these problems. For the first page or two it's fairly easy to come up with SOME solution but it might not be the prettiest thing. There aren't too many people on PE that use R to solve the problems so I wanted to see if a group of people would offer up solutions (pretty or ugly - I like to see both) coded in R. Some of them like I said don't even need programming but even for the ones that we can come up with an analytic solution for can have some nice code to do the job as well.

 

[Dason]

Problem 79:
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Spoiler

To be honest I just eyeballed this one. It would be more work to write up code to figure this out then it is to just look at the file and work it out yourself. I'll probably write something just for the heck of it at some point...

The answer if you're interested is:

Spoiler

73162890

 

[Dason]

Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Hint:

Spoiler

I only got this one after somebody hinted that the algorithm for this should be O(n^2) whereas brute force is O(n!). Ok so it's not much of a hint but it's what got me to the solution.

My solution:

Spoiler

k <- readLines("triangle.txt")
k <- strsplit(k, " ")
k <- lapply(k, as.numeric)

for(i in 2:100){
  for(j in 1:length(k[[i]])){
    k[[i]][j] <- k[[i]][j] + max(k[[i-1]][j-1], k[[i-1]][j], na.rm = T)
  }
}

max(k[[100]])

 

[Dason]

And if somebody wants to PM the username and password... I kind of forgot them. I'm pretty sure the account is under my email address so I could reset the password but I don't want to lock anybody else out. I used my personal PE account to do that last one but I would like to get the TS account credit for it.

Edit: Thanks Jake!

Also - I went and did #18 because it's the same exact problem except smaller. The idea there was that you actually can brute force the solution for #18 but it would take FOREVER to bruteforce #67.

 

[ledzep]

Some really cool R programming. Natty! My level of R programming is next to nothing. But hey, anything that helps me improve my R skills, I'll jump into. I'll be interested in PE.Count me in (but don't expect anything from me though). What takes you 5 mins to solve will keep me reeling for weeks if not months!