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