Jeremy is right!

Jeremy is right!

Jan 27

Study Finds High-Fructose Corn Syrup Contains Mercury – washingtonpost.com

Jeremy is right! High-fructose corn syrup really is causing political unrest in America, world instability, the global financial crisis, turmoil in the middle east, conflict among Jupiter’s moons, and near-certain destruction of earth (and Jupiter).

… Sorry, I got a bit carried away.

That washintonpost.com article is a republication of this article at healthday.com.

The article cites this study:
Mercury from chlor-alkali plants: measured concentrations in food product sugar

Project Euler : Problem 55

Project Euler : Problem 55

Jan 17

Problem 55, in short, says “How many Lychrel numbers are there below ten-thousand?”

I didn’t know what a Lychrel number was until I read the explanation. Here it is:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

At first I made the mistake of thinking that a number was Lychrel if it does produce a palindromic number within 50 iterations. Then I realized my mistake: a number is Lychrel if it doesn’t produce a palindromic number within 50 iterations.

Here is what I came up with in Clojure to determine the number of Lychrel numbers less than 10,000:

(import '(java.math BigInteger))

(defn reverse-str [s]
  (apply str (reverse s)))

(defn reverse-int [n]
  (BigInteger. (reverse-str (str n))))

(defn add-reverse [n]
  (+ n (reverse-int n)))

(defn lychrel? [n iterations]
  (if (< iterations 1)
    true
    (let [i (add-reverse n)
          s (str i)]
      (if (= (reverse-str s) s)
        false
        (recur i (- iterations 1))))))

(println (count (filter #(lychrel? % 49) (range 10000))))

Project Euler : Problem 97

Project Euler : Problem 97

Jan 17

I just implemented a solution to problem 97 in clojure!

Problem 97 is to “Find the last ten digits of the non-Mersenne prime:
28433 × 2^7830457 + 1.”

My solution in clojure ran in 82165.759 milliseconds, which Google says is 1.36 minutes.

Here’s my implementation:

(require ‘math)
(time (rem (+ (* 28433 (expt 2 7830457)) 1) 10000000000))

My solution uses an external clojure library that implements the function expt (i.e. exponentiation). That library is posted for download here.

Project Euler : Problem 7 – Part 2

Project Euler : Problem 7 – Part 2

Jan 17

I’m learning a new language called clojure and wanted to re-implement my solution to problem 7 in it. Here it is:

(defn list-primes
  ([n] (list-primes n [2] 3))
  ([n primes i]
    (if (>= (count primes) n)
      primes
      (if (not-any? #(= (rem i %) 0) primes)
        (recur n (conj primes i) (+ i 2))
        (recur n primes (+ i 2))))))
(println (nth (list-primes 10001) 10000))

Project Euler : Problem 7

Project Euler : Problem 7

Jan 16

Problem 7 is to “Find the 10,001^st prime.”

Here’s a brute force approach in Ruby:

def primes(n)  primes = [2]  i = 3  until primes.length >= n    primes << i unless primes.any? { |p| i % p == 0 }    i += 2  end  primesend

# What is the 10,001st prime?puts primes(10001)[10001-1]

I’m running Ruby 1.9.1 RC1, and on my 2.2GHz Core2Duo MacBook, here are the timed execution results (I’ve masked the result so you can try it yourself):

davidkellis$ time ruby Projects/ruby/primes.rb ######

real	0m9.125suser	0m9.066ssys	0m0.035s

I bet a C implementation would run in less than two seconds.

Project Euler : Problem 1

Project Euler : Problem 1

Jan 15

I solved problem 1 with the knowledge that the sum of an arithmetic sequence is:

Problem 1 says:
“Add all the natural numbers below one thousand that are multiples of 3 or 5.”

So, the sum of all natural numbers between 0 and 999 (inclusive) that are multiples of 3 and 5 is equal to the sum of the natural numbers that are multiples of 3, plus the sum of the natrual numbers that are multiples of 5, minus the sum of the natural numbers that are multiples of 15.

We subtract the sum of the multiples of 15 because multiples of 15 are double counted when we add the sum of the multiples of 3 to the sum of the multiples of 5.

Here is a quick example that illustrates why we subtract the sum of the multiples of 15:

This is the sum of the multiples of 3 from 0 through 15:
0 + 3 + 6 + 9 + 12 + 15

This is the sum of the multiples of 5 from 0 through 15:
0 + 5 + 10 + 15

Now when we sum those two sums, we double count 15:
(0 + 3 + 6 + 9 + 12 + 15) + (0 + 5 + 10 + 15)

We subtract the sum of the multiples of 15 to ensure that multiples of 3 and 5 (i.e. multiples of 15) are only counted once (instead of twice – double counting them):
(0 + 3 + 6 + 9 + 12 + 15) + (0 + 5 + 10 + 15) – (0 + 15)

So, to solve the problem I computed the sum of the multiples of 3 from 0 to 999:
0 + 3 + 6 + … + 999 = 334 * (0 + 999)/2 = 166833

Where did 334 come from? That’s n in the equation above. According to wikipedia:

If the initial term of an arithmetic progression is a₁ and the common difference of successive members is d, then the nth term of the sequence is given by:

and in general

I computed n as follows:
a_n = a₁ + (n – 1) * d
=> 999 = 0 + (n – 1) * 3
=> 333 = 0 + (n – 1)
=> 333 = n – 1
=> 334 = n
=> n = 334

So, the sum of the multiples of 3 from 0 to 999 is:
0 + 3 + 6 + … + 999 = 334 * (0 + 999) / 2 = 166833

Now to compute the sum of the multiples of 5 from 0 to 995:
0 + 5 + 10 + … + 995 = 200 * (0 + 995) / 2 = 99500

I computed n = 200 as follows:
a_n = a₁ + (n – 1) * d
=> 995 = 0 + (n – 1) * 5
=> 199 = 0 + (n – 1)
=> 199 = n – 1
=> 200 = n
=> n = 200

So, the sum of the multiples of 5 from 0 to 995 is:
0 + 5 + 10 + … + 995 = 200 * (0 + 995) / 2 = 99500

Finally, we compute the sum of the multiples of 15 from 0 to 990:
0 + 15 + 30 + … + 990 = 67 * (0 + 990) / 2 = 33165

I computed n = 67 by:
a_n = a₁ + (n – 1) * d
=> 990 = 0 + (n – 1) * 15
=> 66 = 0 + (n – 1)
=> 66 = n – 1
=> 67 = n
=> n = 67

So, the sum of the multiples of 15 from 0 to 990 is:
0 + 15 + 30 + … + 990 = 67 * (0 + 990) / 2 = 33165

The final sum is:
(sum of multiples of 3) + (sum of multiples of 5) – (sum of multiples of 15)
=> 166833 + 99500 – 33165 = 233168

So, the sum of the natural numbers that are multiples of 3 or 5 and less than 1000 is 233168.