Project Euler Problem 52 Solution

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

My solution in Ruby:

i = 1;
answer = nil;

while answer == nil
  i += 1
  x = i * 2
  base = Array.new(x.to_s.scan(/./))
  matchbase = true
  for t in 3..6
    break if matchbase == false
    x = i * t
    digits = Array.new(x.to_s.scan(/./))
    digits.each { |d| matchbase = false if base.index(d) == nil }
  end
  answer = i if matchbase == true
end
puts "Answer: #{answer}"

Project Euler Problem 48 Solution

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).

My solution in Ruby:

sum = 0
for i in 1..1000 do
  sum += i**i
end
str = sum.to_s

puts str[str.length - 10,str.length]

UPDATE

s = 0
(1..1000).inject { |s, x| s + x ** x } % (10 ** 10)
str = s.to_s
puts str[str.length - 10,str.length]

Project Euler Problem 28 Solution

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21   22   23   24   25
20    7    8    9   10
19    6    1    2   11
18    5    4    3   12
17   16   15   14   13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

My solution in Ruby:

corners = [1]
num = 1
add = 2
500.times do
  4.times do
    num += add
    corners << num
  end
  add += 2
end
sum = 0
corners.each { |c| sum += c }
puts sum

Project Euler Problem 25 Solution

The Fibonacci sequence is defined by the recurrence relation:

F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

F_(1) = 1
F_(2) = 1
F_(3) = 2
F_(4) = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

My solution in Ruby:

t1, t2, term = 1, 2, 3
loop do
  temp = t1 + t2
  t1 = t2
  t2 = temp
  term += 1
  temp_s = temp.to_s
  break if temp_s.length >= 1000
end
puts term
Enhanced by Zemanta

Project Euler Problem 17 Solution

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

My solution in Ruby:

@@words = { 1 => "one",2 => "two",3 => "three",4 => "four",5 => "five",
6 => "six",7 => "seven",8 => "eight",9 => "nine",10 => "ten",11 => "eleven",12 => "twelve",
13 => "thirteen",14 => "fourteen",15 => "fifteen",16 => "sixteen",17 => "seventeen",
18 => "eighteen",19 => "nineteen",20 => "twenty",30 => "thirty",40 => "forty",50 => "fifty",
60 => "sixty",70 => "seventy",80 => "eighty",90 => "ninety",100 => "hundred",
1000 => "thousand",0 => "" }
count = 0;

def one_to_ninetynine(base)
  icount = 0
  for i in 1..19 do
    icount += base + @@words[i].length
  end
  j = 10
  until j == 90
    j += 10
    icount += base + @@words[j].length
    for k in 1..9 do
      icount += base + @@words[j].length + @@words[k].length
    end
  end
  icount
end

count += one_to_ninetynine(0)

for l in 1..9 do
  count += @@words [l].length + (@@words[100].length)
  count += one_to_ninetynine(@@words[l].length + (@@words[100].length) + 3)
end
count += @@words[1].length + @@words[1000].length

puts count

Project Euler Problem 14 Solution

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

My solution in Ruby:

highchain = {}
high = 0
1000000.downto(1) do |i|
  links = 0
  result = i
  loop do
    links += 1
    if result.odd?
      result = (result * 3) + 1
    else
      result = result / 2
    end
    break if result == 1
  end
  highchain = {i, links} if links > high
  high = links if links > high
end
highchain.each { |k,v| puts "#{k} has the longest chain of #{v} links!"}

Project Euler Problem 13 Solution

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
(numbers omitted)

My solution in Ruby:

 numbers = [
37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690 ]

sum = 0
numbers.each do |i|
  sum += i
end
sum_s = sum.to_s
puts sum_s[0,10]

Project Euler Problem 12 Solution

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

My solution in Ruby:

def calc_divisors(num)
  res=[1]
  2.upto(Math.sqrt(num).floor) do |i|
    if num % i == 0
      res << i
    end
  end
  res.reverse.each do |i|
    res << num / i
  end
  res.uniq
end

triangle = 0
count = 0
while calc_divisors(triangle).count < 500
  count += 1
  triangle += count
end
puts triangle

This code takes a little while to run, and so far, this is my favourite Project Euler Solution. I did originally try brute-forcing the divisors for each number, but as you can imagine, testing half of every possible candidate for numbers in the millions meant that the loops were getting too long. Interestingly, I never let that original method find the answer so instead I hit google, looking for a faster way. I discovered a lot about sieves and old math geniuses, but the the best example I found was using prime factorials. The function ‘calc_divisors’ in the above code seems to be the fastest way I could find to determine the factors of a specified Integer. If you think there is a faster way, I’d be interested to hear.