Odd period square roots


Fork me on GitHub
2015-07-03

Problem 064: Odd period square roots

Description:

All square roots are periodic when written as continued fractions and can be written in the form:

sqrt(N) = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + ... )))

For example, let us consider sqrt(23):

sqrt(23) 
 = 4 + sqrt(23) - 4 
 = 4 + 1 / ( 1 / ( sqrt(23) - 4 ) ) 
 = 4 + 1 / ( 1 + ( sqrt(23) - 3 ) / 7)

If we continue we would get the following expansion:

sqrt(23) = 4 + 1/(1 + 1/(3 + 1/(1 + 1/(8 + ... ))))

The process can be summarised as follows:

a Step 1 Step 1 Step 1
a0 4, 1/(sqrt(23) - 4 1*(sqrt(23) + 4) / 7 1 + (sqrt(23) - 3)/7
a1 1, 7/(sqrt(23) - 3 7*(sqrt(23) + 3) / 14 3 + (sqrt(23) - 3)/2
a2 3, 2/(sqrt(23) - 3 2*(sqrt(23) + 3) / 14 1 + (sqrt(23) - 4)/7
a3 1, 7/(sqrt(23) - 4 7*(sqrt(23) + 4) / 7 8 + (sqrt(23) - 4)/1
a4 8, 1/(sqrt(23) - 4 1*(sqrt(23) + 4) / 7 1 + (sqrt(23) - 3)/7
a5 1, 7/(sqrt(23) - 3 7*(sqrt(23) + 3) / 14 3 + (sqrt(23) - 3)/2
a6 3, 2/(sqrt(23) - 3 2*(sqrt(23) + 3) / 14 1 + (sqrt(23) - 4)/7
a7 1, 7/(sqrt(23) - 4 7*(sqrt(23) + 4) / 7 8 + (sqrt(23) - 4)/1

It can be seen that the sequence is repeating. For conciseness, we use the notation sqrt(23) = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

sqrt( 2) = [1;(2)],         period=1
sqrt( 3) = [1;(1,2)],       period=2
sqrt( 5) = [2;(4)],         period=1
sqrt( 6) = [2;(2,4)],       period=2
sqrt( 7) = [2;(1,1,1,4)],   period=4
sqrt( 8) = [2;(1,4)],       period=2
sqrt(10) = [3;(6)],         period=1
sqrt(11) = [3;(3,6)],       period=2
sqrt(12) = [3;(2,6)],       period=2
sqrt(13) = [3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N <= 13, have an odd period.

How many continued fractions for N <= 10000 have an odd period?


Solution:
v###
 #####
0
">>1-:0\951p11p021p131v      v12g14    p150 p13/g<
I       vp01g03_v#-g01:_v#- <>g+31g/ :31g*21g-21v1
i   @   >:30p:20 g\/+2/: 30g^^12p14:<>11g21g:*-3 ^
 *  .           >    #$ >$30g::*11g-||+g15-1g13p<
"+  $   ^p02:p010g11p1<       v\+1\<>>0>\#+ #1:#$_v
>^^_^#-2:                     <   _^#          %2$<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

For this I had to re-use my old integer-squareroot implementation and I ported an algorithm for calculating the continued fraction to befunge.

The rest is just iterating through all the values and trying to optimize for speed.

Here two useful snippets I made while solving this puzzle:

  • Calculating the sum of an zero-terminated array on the stack: >\# :#+_+
  • Calculating the count of an zero-terminated array on the stack: 0>\#+ #1:#$_$

Interpreter steps: 24 936 143
Execution time (BefunExec): 5.80s (4.30 MHz)
Program size: 51 x 9 (fully conform befunge-93)
Solution: 1322
Solved at: 2015-07-03



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript