cp's OEIS Frontend

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

%I A004215 M4349 #141 Apr 26 2025 08:22:46
%S A004215 7,15,23,28,31,39,47,55,60,63,71,79,87,92,95,103,111,112,119,124,127,
%T A004215 135,143,151,156,159,167,175,183,188,191,199,207,215,220,223,231,239,
%U A004215 240,247,252,255,263,271,279,284,287,295,303,311,316,319,327,335,343
%N A004215 Numbers that are the sum of 4 but no fewer nonzero squares.
%C A004215 Lagrange's theorem tells us that each positive integer can be written as a sum of four squares.
%C A004215 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 A004215 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 A004215 A002828(a(n)) = 4; A025427(a(n)) > 0. - _Reinhard Zumkeller_, Feb 26 2015
%C A004215 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 A004215 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 A004215 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 A004215 G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 12.
%D A004215 E. Poznanski, 1901. Pierwiastki pierwotne liczb pierwszych. Warszawa, pp. 1-63.
%D A004215 W. Sierpiński, 1925. Teorja Liczb. pp. 1-410 (p. 125).
%D A004215 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A004215 David Wells, The Penguin Dictionary of Curious and Interesting Numbers, entry 4181.
%H A004215 T. D. Noe, <a href="/A004215/b004215.txt">Table of n, a(n) for n = 1..10000</a>
%H A004215 David S. Bettes, <a href="/A004214/a004214.pdf">Letter to N. J. A. Sloane, Nov 05 1976</a>
%H A004215 Richard T. Bumby, <a href="http://www.math.rutgers.edu/~bumby/squares1.pdf">Sums Of Four Squares</a>
%H A004215 International Union of Crystallography, <a href="http://ww1.iucr.org/iucr-top/comm/cteach/pamphlets/16/node5.html">Cubic structures</a>.
%H A004215 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 A004215 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 A004215 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 A004215 Steve Waterman, <a href="http://watermanpolyhedron.com/MISSING.html">Missing numbers formula</a>
%H A004215 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquareNumber.html">Square Number</a>
%H A004215 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem">Lagrange's four-square theorem</a>.
%H A004215 <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>
%F A004215 a(n) = A055039(n)/2. - _Ray Chandler_, Jan 30 2009
%F A004215 Numbers of the form 4^i*(8*j+7), i >= 0, j >= 0. [A.-M. Legendre & C. F. Gauss]
%F A004215 Products of the form A000302(i)*A004771(j), i, j >= 0. - _R. J. Mathar_, Nov 29 2006
%F A004215 a(n) = 6*n + O(log(n)). - _Charles R Greathouse IV_, Dec 19 2013
%F A004215 Conjecture: The number of terms < 2^n is A023105(n) - 2. - _Tilman Neumann_, Sep 20 2020
%e A004215 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 A004215 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 A004215 N:= 1000: # to get all terms <= N
%p A004215 {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 A004215 Sort[Flatten[Table[4^i(8j + 7), {i, 0, 2}, {j, 0, 42}]]] (* _Alonso del Arte_, Jul 05 2005 *)
%t A004215 Select[Range[120], Mod[ #/4^IntegerExponent[ #, 4], 8] == 7 &] (* _Ant King_, Oct 14 2010 *)
%o A004215 (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 A004215 (PARI) isA004215(n)= n\4^valuation(n,4)%8==7 \\ _M. F. Hasler_, Mar 18 2011
%o A004215 (Haskell)
%o A004215 a004215 n = a004215_list !! (n-1)
%o A004215 a004215_list = filter ((== 4) . a002828) [1..]
%o A004215 -- _Reinhard Zumkeller_, Feb 26 2015
%o A004215 (Python)
%o A004215 def valuation(n, b):
%o A004215     v = 0
%o A004215     while n > 1 and n%b == 0: n //= b; v += 1
%o A004215     return v
%o A004215 def ok(n): return n//4**valuation(n, 4)%8 == 7 # after _M. F. Hasler_
%o A004215 print(list(filter(ok, range(344)))) # _Michael S. Branicky_, Jul 15 2021
%o A004215 (Python)
%o A004215 from itertools import count, islice
%o A004215 def A004215_gen(startvalue=1): # generator of terms >= startvalue
%o A004215     return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==7,count(max(startvalue,1)))
%o A004215 A004215_list = list(islice(A004215_gen(),30)) # _Chai Wah Wu_, Jul 09 2022
%o A004215 (Python)
%o A004215 def A004215(n):
%o A004215     def bisection(f,kmin=0,kmax=1):
%o A004215         while f(kmax) > kmax: kmax <<= 1
%o A004215         kmin = kmax >> 1
%o A004215         while kmax-kmin > 1:
%o A004215             kmid = kmax+kmin>>1
%o A004215             if f(kmid) <= kmid:
%o A004215                 kmax = kmid
%o A004215             else:
%o A004215                 kmin = kmid
%o A004215         return kmax
%o A004215     def f(x): return n+x-sum(((x>>(i<<1))-7>>3)+1 for i in range(x.bit_length()>>1))
%o A004215     return bisection(f,n,n) # _Chai Wah Wu_, Feb 14 2025
%Y A004215 Complement of A000378.
%Y A004215 Cf. A002828, A055039, A072401, A125084, A134738, A134739, A055045, A055046, A234000.
%Y A004215 Cf. A000118 (ways to write n as sum of 4 squares), A025427.
%K A004215 nonn,nice,easy
%O A004215 1,1
%A A004215 _N. J. A. Sloane_ and _J. H. Conway_
%E A004215 More terms from Arlin Anderson (starship1(AT)gmail.com)
%E A004215 Additional comments from _Jud McCranie_, Mar 19 2000