A103266 Minimal number of squares needed to sum to Fibonacci(n+1).

1, 2, 3, 2, 2, 2, 3, 2, 4, 2, 1, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 4, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 4

Offset

1,2

Comments

Since every positive integer is the sum of four squares, no term is greater than 4. Also, since any positive integer not of the form 4^k(8m+7) is the sum 3 or fewer squares, the next occurrences of a(n)=4 are at n = 45, 57, 69, 81, 83, 93, .... - John W. Layman, Mar 30 2005

References

Hardy and Wright, An Introduction to the Theory of Numbers, Fourth Ed., Oxford, Section 20.10.

Links

Hans Havermann, Table of n, a(n) for n = 1..1400 (terms 1..465 from Antti Karttunen)

Formula

a(n) = A002828(A000045(n+1)).

Example

Fibonacci(10+1) = 89 = 25+64, so a(10)=2.

Mathematica

Array[If[First[#] > 0, 1, Length@ First@ Split@ # + 1] &@ SquaresR[Range@ 4, Fibonacci@ #] &, 50, 2] (* Michael De Vlieger, Nov 13 2018, after Harvey P. Dale at A002828 *)

Prog

(PARI)
istwo(n:int) = { my(f); if(n<3, return(n>=0); ); f=factor(n>>valuation(n, 2)); for(i=1, #f[, 1], if(bitand(f[i, 2], 1)==1&&bitand(f[i, 1], 3)==3, return(0))); 1 };
isthree(n:int) = { my(tmp=valuation(n, 2)); bitand(tmp, 1)||bitand(n>>tmp, 7)!=7 };
A002828(n) = if(issquare(n), !!n, if(istwo(n), 2, 4-isthree(n))); \\ From A002828
A103266(n) = A002828(fibonacci(1+n)); \\ Antti Karttunen, Nov 10 2018

Crossrefs

Cf. A000045, A002828.

Sequence in context: A324983 A147561 A210659 * A185150 A299229 A289496

Adjacent sequences: A103263 A103264 A103265 * A103267 A103268 A103269

Keyword

nonn

Author

Giovanni Teofilatto, Mar 20 2005

Extensions

Corrected and extended by John W. Layman, Mar 30 2005

Extended by Ray Chandler, May 16 2005

Status

approved