Source

project-euler / project-euler / 137 / analysis.txt

Full commit
Shlomi Fish 4411cf5 












Shlomi Fish dc5b4ae 






















Shlomi Fish 8ffc65f 
Shlomi Fish dc5b4ae 
Shlomi Fish 8ffc65f 
Shlomi Fish dc5b4ae 
Shlomi Fish 8ffc65f 
Shlomi Fish dc5b4ae 
Shlomi Fish 8ffc65f 
Shlomi Fish dc5b4ae 
Shlomi Fish 8ffc65f 




F[n] = 1/sqrt(5) * { [ (1 + sqrt(5)) / 2 ]^n - [ (1 - sqrt(5)) / 2 ] ^ n }

$s = sqrt(5)

Therefore:

[ Given limits according to the |q| <= 1 ]

A_F(x) = 1/$s * { x(1+$s)/2/[ 1 - x(1+$s)/2] - x(1-$s)/2/[1 - x(1-$s)/2] } =

x/(2*$s) * { (1+$s)/[1 - x(1+$s)/2] - (1-$s)/[1 - x(1-$s)/2] } =

x/(2*$s) * { 1/[1/(1+$s) - x/2] - 1/[1/(1-$s) - x/2] } =

    [y = x/2]

y*$s * {1/[1/(1+$s) - y] - 1/[1/(1-$s) - y] } =

    [z = 1/y]

$s * { 1 / [z/(1+$s) - 1] - 1 / [z/(1-$s) - 1] } = N

$s * [z/(1-$s)-1 - z/(1+$s) + 1 ]/[z/(1+s)-1]/[z/(1-s)-1] = N

$s * z * (1/(1-$s)-1/(1+$s)) = N[z/(1+$s)-1][z/(1-s)-1]

    [ * (1+$s) * (1-$s)]

$s * $z * (1+$s-1+$s) = N[z-(1+$s)][z-(1-$s)]

    2 $s^2 * $z = N [ z^2 - 2z + (1-$s^2)]

    $s^2 = 5

    10z = N [ z^2 - 2z - 4 ]

    z^2 - (2+10/N)z - 4 = 0

    z = [ -b +/- sqrt(b^2-4ac) ] / (2*a)

    z is rational iff b^2-4ac is a square of a rational number:

    ∆ = (2+10/N)^2+16 = 4[ (1+5/N)^2+4 ] = 4[ (N+5)^2/N^2 + 4 ]

    ∆ = 4[ [ (N+5)^2+4N^2 ] / N^2 ]

        rational iff (N+5)^2+4N^2 is a whole square.