IBM Ponder This 03-19 Solved

Credited with solving this puzzle:

Ponder This Challenge:

Every real number can be approximated as a ratio of two integers. For example, pi is close to 22/7 but even closer to 3138/999; and there is an even better approximation with a denominator < 1000 (what is it?).

We define m=BAT(x,N) as the denominator, m, of a fraction k/m which is the best approximation for x with denominator < N.

Let N1 be the number of electrons in one coulomb of electric charge.

Let N2 be energy (measured in electron volts) released in the fusion of 1,000 deuterium atoms and 1,000 tritium atoms to form 1,000 He-4 atoms and 1,000 neutrons.

Find two non-square integers n1 and n2 such that b1=BAT(sqrt(n1),N1)=BAT(sqrt(n2),N1) and b2=BAT(sqrt(n1),N2)=BAT(sqrt(n2),N2) and both b1 and b2 are prime numbers.

Bonus question: for the smallest solution that also satisfy BAT(sqrt(n1),10000)=BAT(sqrt(n2),10000), what is the connection between BAT(sqrt(n1),10000) and IBM? Hint: see April 2011’s challenge.

Let me explain this question a little more plainly:

• An irrational number can be approximated by a rational number. Pi for instance can’t be perfectly represented by a ratio of two numbers but some get pretty close, like 22/7.
• As you look at larger and larger denominators you can find fractions that get even closer.  This problem is all about finding the closest fraction without going over a specific denominator.
• There are two denominator limits, one is a large number based on the charge of a Coulomb and the other a large number based on a fusion reaction.  (Coulomb limit is 6.2415093414×10^18 per wikipedia and the Fusion limit is 1.758×10^10 if you solve the nuclear reaction)
• The challenge involves selecting a number, looking at its square root (which will be irrational because we are only selecting numbers that aren’t squares) and then finding the best fraction to approximate this number by a fraction with a denominator less than the Coulomb limit and then again with a fraction with a denominator up to the Fusion limit.
• We need to find two numbers whose best fractions up to these limits happen to be the exact same denominators AND these denominators have to be prime too 🙂

This problem screamed out to me that continued fractions might be the right tool to pull out of the toolbox.  The problem is that I have never worked with continued fractions and honestly have always been a little intimidated by them, so this was a fabulous opportunity for me to roll up my sleeves and make myself learn them!

A continued fraction is a representation of a number by a recursive fraction like this one here for Pi:

(For which the shorthand is )

What I was banking on was that each level of this continued fraction we can collapse the fraction to a single fraction that approximates the value.  I developed code to algorithmically construct the continued fraction for a given number and then record the best fraction up to the denominator limits.  If these best denominators are prime, I record the number with its denominators.  If I encounter two numbers that share denominators I have a solution.

I had to really get into a lot of tricky stuff on how to calculate continuous fractions and how to deal with the incredibly large resultant numbers without overflowing.  I also enhanced the algorithm to look for semi-convergent values, these are best fractions that can be found between two steps in the convergent fractions that come out of the continued fraction.

Another interesting challenge I had to deal with was determining if very large numbers were prime.  Normally I cache a large number of primes (~ first 10,000) and then check against for factors, but the root of these numbers exceeded my maximum primes in my list and checking deterministically for the gap (or expanding the list) is just really not efficient for the amount of processing time it would take to factor these huge numbers.  After a bit of research I decided to use a probabilistic approach to determine if a number was prime, the one that seemed best suited is called a Miller-Rabin Primality Test .  I spent a very long time looking for an existing implementation and every piece of code I found and translated simply didn’t work so I ended up just writing my own from scratch; this took a bit of doing but works great and because of the test values I am using internally it is actually deterministic up to the limits we are dealing with and it is super fast.

After running the code I get the following solution pair (this also satisfies the extra-credit requirements too which I didn’t talk about above):

Matching Value One: 477

• Coulomb Limit
  • Fraction: 129496190370346472379/5929223246159194801
  • Continued Fraction: [21;1,5,3,1,4,10,1,2,2,4,2,2,1,10,4,1,3,5,1,42,1,5,3,1,4,10,1,2,2,4,2,2,1,10,4,1,3,5]
  • Semi-convergent: False
• Fusion Limit
  • Fraction: 376046416221/17217982601
  • Continued Fraction: [21;1,5,3,1,4,10,1,2,2,4,2,2,1,10,4,1,3,5,1,42]
  • Semi-convergent: False
• Extra Credit Limit
  • Fraction: 198747/9100
  • Continued Fraction: [21;1,5,3,1,4,10,1,2,2]
  • Semi-convergent: False

Matching Value Two: 53

• Coulomb Limit
  • Fraction: 43165396790115490793/5929223246159194801
  • Continued Fraction: [7;3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1]
  • Semi-convergent: False
• Fusion Limit
  • Fraction: 125348805407/17217982601
  • Continued Fraction: [7;3,1,1,3,14,3,1,1,3,14,3,1,1,3,14,3,1,1,3,14]
  • Semi-convergent: False
• Extra Credit Limit
  • Fraction: 66249/9100
  • Continued Fraction: [7;3,1,1,3,14,3,1,1,3]
  • Semi-convergent: False

… and the extra credit answer from this is that 9100 is the number of patents IBM was awarded in 2018!