login
Numbers that are the sum of 4 but no fewer nonzero squares.
(Formerly M4349)
97

%I M4349 #129 Apr 18 2024 11:29:23

%S 7,15,23,28,31,39,47,55,60,63,71,79,87,92,95,103,111,112,119,124,127,

%T 135,143,151,156,159,167,175,183,188,191,199,207,215,220,223,231,239,

%U 240,247,252,255,263,271,279,284,287,295,303,311,316,319,327,335,343

%N Numbers that are the sum of 4 but no fewer nonzero squares.

%C Lagrange's theorem tells us that each positive integer can be written as a sum of four squares.

%C If n is in the sequence and k is an odd positive integer then n^k is in the sequence because n^k is of the form 4^i(8j+7). - _Farideh Firoozbakht_, Nov 23 2006

%C Numbers whose cubes do not have a partition as a sum of 3 squares. a(n)^3 = A134738(n). - _Artur Jasinski_, Nov 07 2007

%C A002828(a(n)) = 4; A025427(a(n)) > 0. - _Reinhard Zumkeller_, Feb 26 2015

%C There are infinitely many adjacent pairs (for example, 128n + 111 and 128n + 112 for any n), but never a triple of consecutive integers. - _Ivan Neretin_, Aug 17 2017

%C These numbers are called "forbidden numbers" in crystallography: for a cubic crystal, no reflection with index hkl such that h^2 + k^2 + l^2 = a(n) appears in the crystal's diffraction pattern. - _A. Timothy Royappa_, Aug 11 2021

%D L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 261.

%D E. Poznanski, 1901. Pierwiastki pierwotne liczb pierwszych. Warszawa, pp. 1-63.

%D W. Sierpiński, 1925. Teorja Liczb. pp. 1-410 (p. 125).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D David Wells, The Penguin Dictionary of Curious and Interesting Numbers, entry 4181.

%H T. D. Noe, <a href="/A004215/b004215.txt">Table of n, a(n) for n = 1..10000</a>

%H David S. Bettes, <a href="/A004214/a004214.pdf">Letter to N. J. A. Sloane, Nov 05 1976</a>

%H Richard T. Bumby, <a href="http://www.math.rutgers.edu/~bumby/squares1.pdf">Sums Of Four Squares</a>

%H International Union of Crystallography, <a href="http://ww1.iucr.org/iucr-top/comm/cteach/pamphlets/16/node5.html">Cubic structures</a>.

%H Shuo Li, <a href="https://arxiv.org/abs/2404.08822">The characteristic sequence of the integers that are the sum of two squares is not morphic</a>, arXiv:2404.08822 [math.NT], 2024.

%H Louis J. Mordell, <a href="http://dx.doi.org/10.1093/qmath/os-1.1.276">A new Waring's problem with squares of linear forms</a>, Quart. J. Math., 1 (1930), 276-288 (see p. 283).

%H Saburô Uchiyama, <a href="https://www.jstage.jst.go.jp/article/kyotoms1969/13/1/13_1_301/_pdf">A five-square theorem</a>, Publ. Res. Math. Sci., Vol 13, Number 1 (1977), 301-305.

%H Steve Waterman, <a href="http://watermanpolyhedron.com/MISSING.html">Missing numbers formula</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquareNumber.html">Square Number</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem">Lagrange's four-square theorem</a>.

%H <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>

%F a(n) = A055039(n)/2. - _Ray Chandler_, Jan 30 2009

%F Numbers of the form 4^i*(8*j+7), i >= 0, j >= 0. [A.-M. Legendre & C. F. Gauss]

%F Products of the form A000302(i)*A004771(j), i, j >= 0. - _R. J. Mathar_, Nov 29 2006

%F a(n) = 6*n + O(log(n)). - _Charles R Greathouse IV_, Dec 19 2013

%F Conjecture: The number of terms < 2^n is A023105(n) - 2. - _Tilman Neumann_, Sep 20 2020

%e 15 is in the sequence because it is the sum of four squares, namely, 3^2 + 2^2 + 1^2 + 1^2, and it can't be expressed as the sum of fewer squares.

%e 16 is not in the sequence, because, although it can be expressed as 2^2 + 2^2 + 2^2 + 2^2, it can also be expressed as 4^2.

%p N:= 1000: # to get all terms <= N

%p {seq(seq(4^i * (8*j + 7), j = 0 .. floor((N/4^i - 7)/8)), i = 0 .. floor(log[4](N)))}; # _Robert Israel_, Sep 02 2014

%t Sort[Flatten[Table[4^i(8j + 7), {i, 0, 2}, {j, 0, 42}]]] (* _Alonso del Arte_, Jul 05 2005 *)

%t Select[Range[120], Mod[ #/4^IntegerExponent[ #, 4], 8] == 7 &] (* _Ant King_, Oct 14 2010 *)

%o (PARI) isA004215(n)={ local(fouri,j) ; fouri=1 ; while( n >=7*fouri, if( n % fouri ==0, j= n/fouri -7 ; if( j % 8 ==0, return(1) ) ; ) ; fouri *= 4 ; ) ; return(0) ; } { for(n=1,400, if(isA004215(n), print1(n,",") ; ) ; ) ; } \\ _R. J. Mathar_, Nov 22 2006

%o (PARI) isA004215(n)= n\4^valuation(n,4)%8==7 \\ _M. F. Hasler_, Mar 18 2011

%o (Haskell)

%o a004215 n = a004215_list !! (n-1)

%o a004215_list = filter ((== 4) . a002828) [1..]

%o -- _Reinhard Zumkeller_, Feb 26 2015

%o (Python)

%o def valuation(n, b):

%o v = 0

%o while n > 1 and n%b == 0: n //= b; v += 1

%o return v

%o def ok(n): return n//4**valuation(n, 4)%8 == 7 # after _M. F. Hasler_

%o print(list(filter(ok, range(344)))) # _Michael S. Branicky_, Jul 15 2021

%o (Python)

%o from itertools import count, islice

%o def A004215_gen(startvalue=1): # generator of terms >= startvalue

%o return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==7,count(max(startvalue,1)))

%o A004215_list = list(islice(A004215_gen(),30)) # _Chai Wah Wu_, Jul 09 2022

%Y Complement of A000378.

%Y Cf. A002828, A055039, A072401, A125084, A134738, A134739, A055045, A055046, A234000.

%Y Cf. A000118 (ways to write n as sum of 4 squares), A025427.

%K nonn,nice,easy

%O 1,1

%A _N. J. A. Sloane_ and _J. H. Conway_

%E More terms from Arlin Anderson (starship1(AT)gmail.com)

%E Additional comments from _Jud McCranie_, Mar 19 2000