A055045 -id:A055045 - cp's OEIS frontend

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

7, 15, 23, 28, 31, 39, 47, 55, 60, 63, 71, 79, 87, 92, 95, 103, 111, 112, 119, 124, 127, 135, 143, 151, 156, 159, 167, 175, 183, 188, 191, 199, 207, 215, 220, 223, 231, 239, 240, 247, 252, 255, 263, 271, 279, 284, 287, 295, 303, 311, 316, 319, 327, 335, 343

Offset: 1

N. J. A. Sloane and J. H. Conway

Lagrange's theorem tells us that each positive integer can be written as a sum of four squares.
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
Numbers whose cubes do not have a partition as a sum of 3 squares. a(n)^3 = A134738(n). - Artur Jasinski, Nov 07 2007
A002828(a(n)) = 4; A025427(a(n)) > 0. - Reinhard Zumkeller, Feb 26 2015
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
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

			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.
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.

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.
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 12.
E. Poznanski, 1901. Pierwiastki pierwotne liczb pierwszych. Warszawa, pp. 1-63.
W. Sierpiński, 1925. Teorja Liczb. pp. 1-410 (p. 125).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, entry 4181.

T. D. Noe, Table of n, a(n) for n = 1..10000
David S. Bettes, Letter to N. J. A. Sloane, Nov 05 1976
Richard T. Bumby, Sums Of Four Squares
International Union of Crystallography, Cubic structures.
Shuo Li, The characteristic sequence of the integers that are the sum of two squares is not morphic, arXiv:2404.08822 [math.NT], 2024.
Louis J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).
Saburô Uchiyama, A five-square theorem, Publ. Res. Math. Sci., Vol 13, Number 1 (1977), 301-305.
Steve Waterman, Missing numbers formula
Eric Weisstein's World of Mathematics, Square Number
Wikipedia, Lagrange's four-square theorem.
Index entries for sequences related to sums of squares

Complement of A000378.
Cf. A002828, A055039, A072401, A125084, A134738, A134739, A055045, A055046, A234000.
Cf. A000118 (ways to write n as sum of 4 squares), A025427.

a004215 n = a004215_list !! (n-1)
a004215_list = filter ((== 4) . a002828) [1..]
-- Reinhard Zumkeller, Feb 26 2015

N:= 1000: # to get all terms <= N
{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

Sort[Flatten[Table[4^i(8j + 7), {i, 0, 2}, {j, 0, 42}]]] (* Alonso del Arte, Jul 05 2005 *)
Select[Range[120], Mod[ #/4^IntegerExponent[ #, 4], 8] == 7 &] (* Ant King, Oct 14 2010 *)

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

isA004215(n)= n\4^valuation(n,4)%8==7 \\ M. F. Hasler, Mar 18 2011

def valuation(n, b):
    v = 0
    while n > 1 and n%b == 0: n //= b; v += 1
    return v
def ok(n): return n//4**valuation(n, 4)%8 == 7 # after M. F. Hasler
print(list(filter(ok, range(344)))) # Michael S. Branicky, Jul 15 2021

from itertools import count, islice
def A004215_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==7,count(max(startvalue,1)))
A004215_list = list(islice(A004215_gen(),30)) # Chai Wah Wu, Jul 09 2022

def A004215(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>(i<<1))-7>>3)+1 for i in range(x.bit_length()>>1))
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

a(n) = A055039(n)/2. - Ray Chandler, Jan 30 2009
Numbers of the form 4^i*(8*j+7), i >= 0, j >= 0. [A.-M. Legendre & C. F. Gauss]
Products of the form A000302(i)*A004771(j), i, j >= 0. - R. J. Mathar, Nov 29 2006
a(n) = 6*n + O(log(n)). - Charles R Greathouse IV, Dec 19 2013
Conjecture: The number of terms < 2^n is A023105(n) - 2. - Tilman Neumann, Sep 20 2020

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

Additional comments from Jud McCranie, Mar 19 2000

A234000 Numbers of the form 4^i(8j+1).

Original entry on oeis.org

1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57, 64, 65, 68, 73, 81, 89, 97, 100, 105, 113, 121, 129, 132, 137, 144, 145, 153, 161, 164, 169, 177, 185, 193, 196, 201, 209, 217, 225, 228, 233, 241, 249, 256, 257, 260, 265, 272, 273, 281, 289, 292, 297, 305, 313, 321, 324, 329, 337, 345

Offset: 1

V. Raman, Dec 18 2013

Squares modulo all powers of 2. - Robert Israel, Aug 26 2014
From Peter Munn, Dec 11 2019: (Start)
Closed under multiplication.
Contains all even powers of primes.
A subgroup of the positive integers under the binary operation A059897(.,.). For all n, a(n) has no Fermi-Dirac factor of 2 and if m_k denotes the number of Fermi-Dirac factors of a(n) that are congruent to k modulo 8, m_3, m_5 and m_7 have the same parity. It can further be shown (1) all numbers that meet these requirements are in the sequence and (2) this implies closure under A059897(.,.).
(End)

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A055046 (Numbers of the form 4^i*(8*j+3)).
Cf. A055045 (Numbers of the form 4^i*(8*j+5)).
Cf. A004215 (Numbers of the form 4^i*(8*j+7)).
Cf. A059897, A055044.

N:= 1000: # to get all terms <= N
{seq(seq(4^i*(8*k+1), k = 0 .. floor((N * 4^(-i)-1)/8)),i=0..floor(log[4](N)))}; # Robert Israel, Aug 26 2014

is_A234000(n)=(n/4^valuation(n, 4))%8==1 \\ Charles R Greathouse IV and V. Raman, Dec 19 2013; minor improvement by M. F. Hasler, Jan 02 2014

list(lim)=my(v=List(),t); for(e=0,logint(lim\1,4), t=4^e; forstep(k=t, lim, 8*t, listput(v,k))); Set(v) \\ Charles R Greathouse IV, Jan 12 2017

from itertools import count, islice
def A234000_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==1,count(max(startvalue,1)))
A234000_list = list(islice(A234000_gen(),30)) # Chai Wah Wu, Jul 09 2022

def A234000(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>(i<<1))-1>>3)+1 for i in range((x.bit_length()>>1)+1))
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

a(n) = 6n + O(log n). - Charles R Greathouse IV, Dec 19 2013

a(n) = A055044(n)/2. - Chai Wah Wu, Mar 19 2025

A055046 Numbers of the form 4^i(8j+3).

Original entry on oeis.org

3, 11, 12, 19, 27, 35, 43, 44, 48, 51, 59, 67, 75, 76, 83, 91, 99, 107, 108, 115, 123, 131, 139, 140, 147, 155, 163, 171, 172, 176, 179, 187, 192, 195, 203, 204, 211, 219, 227, 235, 236, 243, 251, 259, 267, 268, 275, 283, 291, 299, 300, 304, 307, 315, 323, 331, 332

Offset: 1

N. J. A. Sloane, Jun 01 2000

Numbers not of the form x^2+y^2+5z^2.

Also values of n such that numbers of the form x^2+n*y^2 for some integers x, y cannot have prime factor of 2 raised to an odd power. - V. Raman, Dec 18 2013

Paolo Xausa, Table of n, a(n) for n = 1..10000
L. J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).

Cf. A004215, A055043, A055045, A055047, A233998, A233999, A234000.

A055046Q[k_] := Mod[k/4^IntegerExponent[k, 4], 8] == 3;
Select[Range[500], A055046Q] (* Paolo Xausa, Mar 20 2025 *)

is(n)=n/=4^valuation(n,4); n%8==3 \\ Charles R Greathouse IV and V. Raman, Dec 19 2013

from itertools import count, islice
def A055046_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==3,count(max(startvalue,1)))
A055046_list = list(islice(A055046_gen(),30)) # Chai Wah Wu, Jul 09 2022

def A055046(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>(i<<1))-3>>3)+1 for i in range(x.bit_length()>>1))
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

a(n) = 6n + O(log n). - Charles R Greathouse IV, Dec 19 2013

a(n) = A055043(n)/2. - Chai Wah Wu, Mar 19 2025

A055042 Numbers of the form 2^(2i+1)(8j+5).

Original entry on oeis.org

10, 26, 40, 42, 58, 74, 90, 104, 106, 122, 138, 154, 160, 168, 170, 186, 202, 218, 232, 234, 250, 266, 282, 296, 298, 314, 330, 346, 360, 362, 378, 394, 410, 416, 424, 426, 442, 458, 474, 488, 490, 506, 522, 538, 552, 554, 570, 586, 602, 616

Offset: 1

N. J. A. Sloane, Jun 01 2000

These are also the numbers not of the form x^2+2y^2+3z^2.

The asymptotic density of this sequence is 1/12. - Amiram Eldar, Mar 29 2025

			42 = 21*2 = 2^(2*0 + 1)*(8*2 + 5) is in the sequence. - _David A. Corneth_, Apr 18 2021

Burton W. Jones, The Arithmetic of Quadratic Forms, Carus Monograph 10, Math. Assoc. America, 1967; Problem 60, p. 204.

David A. Corneth, Table of n, a(n) for n = 1..10000
L. J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).

Cf. A055045.

With[{max = 700}, Flatten[Table[2^(2*i + 1)*(8*j + 5), {i, 0, (Log2[max] - 1)/2}, {j, 0, Floor[(max/2^(2*i + 1) - 5)/8]}]] // Sort] (* Amiram Eldar, Mar 29 2025 *)

upto(n) = { my(res = List()); for(i = 0, logint(n\2, 2), forstep(j = 5, n>>(2*i+1), 8, listput(res, 4^i*2*j) ) ); Set(res) } \\ David A. Corneth, Apr 18 2021

def A055042(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>(i<<1)+1)-5>>3)+1 for i in range(x.bit_length()-1>>1))
    return bisection(f,n,n) # Chai Wah Wu, Mar 19 2025

a(n) = 2*A055045(n). - Chai Wah Wu, Mar 19 2025

A055052 Numbers of the form 4^i(8j+7) or 4^i(8j+5).

Original entry on oeis.org

5, 7, 13, 15, 20, 21, 23, 28, 29, 31, 37, 39, 45, 47, 52, 53, 55, 60, 61, 63, 69, 71, 77, 79, 80, 84, 85, 87, 92, 93, 95, 101, 103, 109, 111, 112, 116, 117, 119, 124, 125, 127, 133, 135, 141, 143, 148, 149, 151, 156, 157, 159, 165, 167, 173, 175

Offset: 1

N. J. A. Sloane, Jun 02 2000

Numbers not of the form x^2+2y^2+8z^2.
The integers that are ratios between the terms constitute the sequence's complement within A003159. - Peter Munn, Feb 07 2024
The asymptotic density of this sequence is 1/3. - Amiram Eldar, Feb 09 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
L. J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).

Disjoint union of A004215 and A055045.

Subsequence of A003159, A097700.

Select[Range[200], MemberQ[{5, 7}, Mod[# / 4^IntegerExponent[#, 4], 8]] &] (* Amiram Eldar, Feb 09 2024 *)

def A055052(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c = n+x
        for i in range(x.bit_length()>>1):
            m = x>>(i<<1)
            c -= (m-5>>3)+(m-7>>3)+2
        return c
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Python

Formula

Extensions

A234000 Numbers of the form 4^i*(8*j+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

PARI

Python

Python

Formula

A055046 Numbers of the form 4^i*(8*j+3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A055042 Numbers of the form 2^(2i+1)*(8*j+5).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A055052 Numbers of the form 4^i*(8j+7) or 4^i*(8j+5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A234000 Numbers of the form 4^i(8j+1).

A055046 Numbers of the form 4^i(8j+3).

A055042 Numbers of the form 2^(2i+1)(8j+5).

A055052 Numbers of the form 4^i(8j+7) or 4^i(8j+5).