A023105 -id:A023105 - 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

A005578 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)-1.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462, 10923, 21846, 43691, 87382, 174763, 349526, 699051, 1398102, 2796203, 5592406, 11184811, 22369622, 44739243, 89478486, 178956971, 357913942, 715827883, 1431655766, 2863311531, 5726623062, 11453246123

Offset: 0

N. J. A. Sloane

Might be called the "Arima sequence" after Yoriyuki Arima who in 1769 constructed this sequence as the number of moves of the outer ring in the optimal solution for the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017
Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1) = u(k) + v(k), v(k+1) = u(k) + w(k), w(k+1) = v(k) + w(k); let M(k) = Max(u(k), v(k), w(k)); then a(n) = M(n). - Benoit Cloitre, Mar 25 2002
Unimodal analog of Fibonacci numbers: a(n+1) = Sum_{k=0..n/2} A071922(n-k, n-2*k). Based on the observation that F_{n+1} = Sum_{k} binomial (n-k, k). - Michele Dondi (bik.mido(AT)tiscalinet.it), Jun 30 2002
Numbers n at which the length of the symmetric signed digit expansion of n with q=2 (i.e., the length of the representation of n in the (-1,0,1)2 number system) increases. - _Ralf Stephan, Jun 30 2003
Row sums of Riordan array (1/(1-x), x/(1-2*x^2)). - Paul Barry, Apr 24 2005
For n > 0, record-values of A107910: a(n) = A107910(A023548(n)). - Reinhard Zumkeller, May 28 2005
2^(n+1) = 2*a(n) + 2*A001045(n) + A000975(n-1); e.g., 2^6 = 64 = 2*a(5) + 2*A001045(5) + 2*A000975(4) = 2*11 + 2*11 + 2*10. Let a(n), A001045(n) and A000975(n-1) = the legs of a triangle (a, b, c). Then a(n-1), A001045(n-1) and A000975(n-2) = (S-c), (S-b), (S-a), where S = the triangle semiperimeter. Example: a(5), A001045(5) and A000975(4) = triangle (a, b, c) = (11, 11, 10). Then a(4), A001045(4), A000975(3) = (S-c), (S-b), (S-a) = (6, 5, 5). - Gary W. Adamson, Dec 24 2007
a(n) is the number of length-n binary representations of a nonnegative integer that is divisible by 3. The initial digits are allowed to be 0's. a(4) = 6 because we have 0000, 0011, 0110, 1001, 1100, 1111. - Geoffrey Critzer, Jan 13 2014
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 0, 1; 0, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 1, 0, 1; 0, 1, 1]. - R. J. Mathar, Feb 04 2014
With 0 prefixed, this sequence is an autosequence of the first kind because the sequence of first differences A001045 is. Its companion is A052950. - Paul Curtz, Dec 18 2018, edited by M. F. Hasler, Dec 21 2018
Apparently, the sequence gives the distinct values taken by A129761, the first differences of fibbinary numbers. - Rémy Sigrist, Oct 26 2019
The sequence with offset 1 can be generated in three steps starting with A158780. First, put in alternate signs (1, -1, 1, -2, 2, -4, ...) and take the inverse; getting (1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...). Take the invert transform of the latter, resulting in the sequence. It follows from the inverti transform being 1, 1, 0, 1, 1, 2, 3, ... that (for example), a(9) = 171 = (1, 1, 0, 1, 1, 2, 3, 5, 8) dot (86, 43, 0, 11, 6, 6, 6, 5, 8) = (86 + 43 + 0 + 11 + 6 + 6 + 6 + 5 + 8). A similar procedure is shown in the Aug 08 2019 comment of A006356. - Gary W. Adamson, Feb 04 2022

R. K. Guy, Graphs and the strong law of small numbers. Graph theory, combinatorics and applications. Vol. 2 (Kalamazoo, MI, 1988), 597-614, Wiley-Intersci. Publ., Wiley, New York, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Sujith Uthsara Kalansuriya Arachchi, Hung Viet Chu, Jiasen Liu, Qitong Luan, Rukshan Marasinghe, and Steven J. Miller, On a Pair of Diophantine Equations, arXiv:2309.04488 [math.NT], 2023.
Joerg Arndt, Matters Computational (The Fxtbook), p. 315.
Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Fan Chung and Shlomo Sternberg, Mathematics and the Buckyball
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 6, 17.
R. K. Guy, Letter to N. J. A. Sloane, Apr 08 1988 (annotated scanned copy, included with permission)
Clemens Heuberger and Helmut Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Gurmeet Singh Manku and Joe Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 385, 387.
John P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.
Hans Olofsen, Blending functions based on trigonometric and polynomial approximations of the Fabius function, The Arctic University of Norway (Narvik, 2019).
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See p. 16.
Andrew V. Sills and Hua Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623.
Eric Weisstein's World of Mathematics, Walsh Function
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A071922, A072176, A135229.
Bisections: A007583 and A047849.
Cf. also A000975, A001045 (first differences), A129761.
Cf. A006356.

List([0..40],n->(2^(n+1)+3+(-1)^n)/6); # Muniru A Asiru, Dec 22 2018

[(2^(n+1)+3+(-1)^n)/6: n in [0..40]]; // Vincenzo Librandi, Aug 14 2011

A005578:=-(-1+z+z^2)/((z-1)*(2*z-1)*(z+1)); # Simon Plouffe in his 1992 dissertation
with(combstruct):ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), a):ZL1:=Prod(begin_blockP, Z, end_blockP):ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL3), b=ZL3], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n), n=2..34); # Zerinvary Lajos, Mar 08 2008

a=0; Table[a=2^n-a;(a/2+1)/2,{n,5!}] (* Vladimir Joseph Stephan Orlovsky, Nov 22 2009 *)
LinearRecurrence[{2,1,-2}, {1,1,2}, 40] (* G. C. Greubel, Aug 26 2019 *)

a(n)=(2^(n+1)+3+(-1)^n)/6 \\ Charles R Greathouse IV, Mar 22 2016

print([1+2**n//3 for n in range(40)])  # Gennady Eremin, Feb 05 2022

[(2^(n+1)+3+(-1)^n)/6 for n in (0..40)] # G. C. Greubel, Aug 26 2019

a(n) = ceiling(2^n/3).
a(n) = 1 + floor((2^n)/3) (proof by mathematical induction).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
From Paul Barry, Jul 20 2003: (Start)
a(n) = A001045(n) + A000035(n+1), where A000035 = (0, 1, 0, 1, ...).
G.f.: (1 - x - x^2)/((1-x^2)*(1-2*x)). [Guy, 1988];
E.g.f.: (exp(2*x) - exp(-x))/3 + cosh(x) = (2*exp(2*x) + 3*exp(x) + exp(-x))/6. (End)
The 30 listed terms are given by a(0)=1, a(1)=1 and, for n > 1, by a(n) = a(n-1) + a(n-2) + Sum_{i=0..n-4} Fibonacci(i)*a(n-4-i). - John W. Layman, Jan 07 2000
a(n) = (2^(n+1) + 3 + (-1)^n)/6. - Vladeta Jovovic, Jul 02 2002
Binomial transform of A001045(n-1)(-1)^n + 0^n/2. - Paul Barry, Apr 28 2004
a(n) = (1 + A001045(n+1))/2. - Paul Barry, Apr 28 2004
a(n) = Sum_{k=0..n} (-1)^k*Sum_{j=0..n-k} (if((j-k) mod 2)=0, binomial(n-k, j), 0). - Paul Barry, Jan 25 2005
Let M = the 6 X 6 adjacency matrix of a benzene ring, (reference): [0,1,0,0,0,1; 1,0,1,0,0,0; 0,1,0,1,0,0; 0,0,1,0,1,0; 0,0,0,1,0,1; 1,0,0,0,1,0]. Then a(n) = leftmost nonzero term of M^n * [1,0,0,0,0,0]. E.g.: a(6) = 22 since M^6 * [1,0,0,0,0,0] = [22,0,21,0,21,0]. - Gary W. Adamson, Jun 14 2006
Starting (1, 2, 3, 6, 11, 22, ...), = row sums of triangle A135229. - Gary W. Adamson, Nov 23 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), A000975(n-1)]. - Gary W. Adamson, Dec 24 2007
a(n) = 1 + 2^(n-1) - a(n-1) = a(n-1) + 2*a(n-2) - 1 = a(n-2) + 2^(n-2). - Paul Curtz, Jan 31 2009
a(n) = A023105(n+1) - 1. - Carl Joshua Quines, Jul 17 2019

Edited by N. J. A. Sloane, Jun 20 2015

A000224 Number of squares mod n.

Original entry on oeis.org

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, 18, 14, 27, 22, 18, 12, 20, 30, 30, 12, 31, 32, 16, 12, 21, 24, 34, 18, 24, 24, 36, 12

Offset: 1

N. J. A. Sloane

For any n > 2, there are quadratic nonresidues mod n, so a(n) < n. - Charles R Greathouse IV, Oct 28 2022
Conjecture: n^2 == 1 (mod a(n)*(a(n)-1)) if and only if n is an odd prime. - Thomas Ordowski, Apr 13 2025
This conjecture holds at least up to n = 10^8. - Michel Marcus, Apr 13 2025

			The sequence of squares (A000290) modulo 10 reads 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1,... and this reduced sequence contains a(10) = 6 different values, {0,1,4,5,6,9}. - _R. J. Mathar_, Oct 10 2014

T. D. Noe, Table of n, a(n) for n = 1..10000
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget.
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 6.
E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.
Walter D. Stangl, Counting Squares in Z_n, Math. Mag. 69 (1996) 285-289.

Cf. A095972, A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where
   f 2 e = 2 ^ e `div` 6 + 2
   f p e = p ^ (e + 1) `div` (2 * p + 2) + 1
-- Reinhard Zumkeller, Aug 01 2012

A000224 := proc(m)
    {seq( modp(b^2,m),b=0..m-1) };
    nops(%) ;
end proc: # Emeric Deutsch
# 2nd implementation
A000224 := proc(n)
    local a,ifs,f,p,e,c ;
    a := 1 ;
    ifs := ifactors(n)[2] ;
    for f in ifs do
        p := op(1,f) ;
        e := op(2,f) ;
        if p = 2 then
            if type(e,'odd') then
                a := a*(2^(e-1)+5)/3 ;
            else
                a := a*(2^(e-1)+4)/3 ;
            end if;
        else
            if type(e,'odd') then
                c := 2*p+1 ;
            else
                c := p+2 ;
            end if;
            a := a*(p^(e+1)+c)/2/(p+1) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 10 2014

Length[Union[#]]& /@ Table[Mod[k^2, n], {n, 65}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *)
a[2] = 2; a[n_] := a[n] = Switch[fi = FactorInteger[n], {{, 1}}, (fi[[1, 1]] + 1)/2, {{2, }}, 3/2 + 2^fi[[1, 2]]/6 + (-1)^(fi[[1, 2]]+1)/6, {{, }}, {p, k} = fi[[1]]; 3/4 + (p-1)*(-1)^(k+1)/(4*(p+1)) + p^(k+1)/(2*(p+1)), , Times @@ Table[ a[Power @@ f], {f, fi}]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover, Mar 09 2015 *)

a(n) = local(v,i); v = vector(n,i,0); for(i=0, floor(n/2),v[i^2%n+1] = 1); sum(i=1,n,v[i]) \\ Franklin T. Adams-Watters, Nov 05 2006

a(n)=my(f=factor(n));prod(i=1,#f[,1],if(f[i,1]==2,2^f[1,2]\6+2,f[i,1]^(f[i,2]+1)\(2*f[i,1]+2)+1)) \\ Charles R Greathouse IV, Jul 15 2011

from math import prod
from sympy import factorint
def A000224(n): return prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factorint(n).items()) # Chai Wah Wu, Oct 07 2024

a(n) = A105612(n) + 1.
Multiplicative with a(p^e) = floor(p^e/6) + 2 if p = 2; floor(p^(e+1)/(2p + 2)) + 1 if p > 2. - David W. Wilson, Aug 01 2001
a(2^n) = A023105(n). a(3^n) = A039300(n). a(5^n) = A039302(n). a(7^n) = A039304(n). - R. J. Mathar, Sep 28 2017
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (17/(32*sqrt(Pi))) * Product_{p prime} (1 - (p^2+2)/(2*(p^2+1)*(p+1))) * (1-1/p)^(-1/2) = 0.37672933209687137604... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
If p is an odd prime, then a(p) = (p + 1)/2. - Thomas Ordowski, Apr 09 2025

A231396 T(n,k)=Number of (n+1)X(k+1) 0..2 arrays with no element unequal to a strict majority of its horizontal, diagonal and antidiagonal neighbors, with values 0..2 introduced in row major order.

Original entry on oeis.org

3, 7, 4, 14, 8, 7, 33, 38, 15, 12, 78, 90, 100, 20, 23, 189, 363, 311, 272, 31, 44, 482, 1163, 1706, 1096, 740, 52, 87, 1225, 3985, 7844, 8340, 4085, 2061, 95, 172, 3238, 14650, 35696, 55788, 41237, 15732, 5834, 180, 343, 8565, 50088, 184692, 345022, 401240

Offset: 1

R. H. Hardin, Nov 08 2013

Table starts
...3...7.....14......33........78........189........482.......1225.......3238
...4...8.....38......90.......363.......1163.......3985......14650......50088
...7..15....100.....311......1706.......7844......35696.....184692.....873979
..12..20....272....1096......8340......55788.....345022....2502891...16525492
..23..31....740....4085.....41237.....401240....3407422...34218952..319475231
..44..52...2061...15732....217846....3002376...35510853..491895476.6459555901
..87..95...5834...62039...1158551...22654165..374180527.7170248270
.172.180..16521..245850...6261166..172363558.3979476204
.343.351..46969..980361..34110556.1318257485
.684.692.133864.3915982.186830745

			Some solutions for n=4 k=4
..0..0..0..0..0....0..0..1..1..1....0..0..1..1..1....0..1..1..1..1
..1..1..0..0..0....1..1..0..0..0....0..1..0..1..1....1..0..0..0..0
..1..1..1..0..0....1..1..1..0..0....1..0..1..0..0....1..1..0..0..0
..1..1..0..0..0....1..1..0..0..0....1..1..0..0..0....1..1..1..2..2
..1..1..1..0..0....0..0..0..0..0....1..1..1..1..1....1..1..2..2..2

R. H. Hardin, Table of n, a(n) for n = 1..111

Column 1 is A023105(n+2)

Empirical for column k:
k=1: a(n) = 2*a(n-1) +a(n-2) -2*a(n-3)
k=2: a(n) = 2*a(n-1) +a(n-2) -2*a(n-3) for n>5
k=3: [order 18]
k=4: [order 28] for n>31
Empirical for row n:
n=1: a(n) = 4*a(n-1) +a(n-2) -16*a(n-3) +4*a(n-4) +24*a(n-5) -16*a(n-6)
n=2: [order 21]
n=3: [order 83]

A231263 T(n,k)=Number of (n+1)X(k+1) 0..2 arrays with no element unequal to a strict majority of its horizontal and antidiagonal neighbors, with values 0..2 introduced in row major order.

Original entry on oeis.org

2, 3, 6, 4, 15, 22, 7, 32, 89, 86, 12, 83, 304, 547, 342, 23, 211, 1253, 2982, 3381, 1366, 44, 557, 5109, 19503, 29366, 20911, 5462, 87, 1471, 21894, 126851, 302121, 289230, 129329, 21846, 172, 3909, 94234, 866396, 3130708, 4670875, 2848550, 799835, 87382

Offset: 1

R. H. Hardin, Nov 06 2013

Table starts
......2........3..........4............7.............12...............23
......6.......15.........32...........83............211..............557
.....22.......89........304.........1253...........5109............21894
.....86......547.......2982........19503.........126851...........866396
....342.....3381......29366.......302121........3130708.........34170727
...1366....20911.....289230......4670875.......77333664.......1350570015
...5462...129329....2848550.....72212345.....1911322499......53369789699
..21846...799835...28054534...1116538567....47238533054....2108712981800
..87382..4946509..276301638..17264116873..1167469879103...83318930054700
.349526.30591143.2721223974.266940042371.28853204049176.3292096503338981

			Some solutions for n=3 k=4
..0..0..0..0..1....0..0..0..0..0....0..0..1..1..1....0..0..1..1..1
..0..0..0..1..0....0..0..0..0..0....0..1..0..0..0....0..1..1..1..1
..1..1..1..0..0....0..1..1..1..0....1..0..2..2..1....2..2..0..0..2
..1..1..1..1..1....1..1..1..0..0....0..2..2..1..1....2..0..0..2..2

R. H. Hardin, Table of n, a(n) for n = 1..161

Column 1 is A047849

Row 1 is A023105(n+1)

Empirical for column k:
k=1: a(n) = 5*a(n-1) -4*a(n-2)
k=2: a(n) = 10*a(n-1) -29*a(n-2) +36*a(n-3) -16*a(n-4)
k=3: [order 7]
k=4: [order 12]
k=5: [order 32]
k=6: [order 67] for n>68
Empirical for row n:
n=1: a(n) = 2*a(n-1) +a(n-2) -2*a(n-3)
n=2: [order 9]
n=3: [order 27] for n>28

A039300 Number of distinct quadratic residues mod 3^n.

Original entry on oeis.org

1, 2, 4, 11, 31, 92, 274, 821, 2461, 7382, 22144, 66431, 199291, 597872, 1793614, 5380841, 16142521, 48427562, 145282684, 435848051, 1307544151, 3922632452, 11767897354, 35303692061, 105911076181, 317733228542, 953199685624

Offset: 0

David W. Wilson

Number of distinct n-digit suffixes of base 3 squares.

In general, for any odd prime p, the number s of quadratic residues mod p^n is given by s = (p^(n+1) + p + 2)/(2p + 2) for even n and s = (p^(n+1) + 2*p + 1)/(2p + 2) for odd n, see A000224. - Lekraj Beedassy, Jan 07 2005

J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 324.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).
Index entries for linear recurrences with constant coefficients, signature (3,1,-3).

Cf. A033113, A000224, A015518, A023105.

List([0..30], n-> (3^(n+1) +6 -(-1)^n)/8); # G. C. Greubel, Jul 14 2019

[(3^(n+1) + 6 + (-1)^(n+1))/8: n in [0..30]]; // Vincenzo Librandi, Apr 21 2012

A039300 := proc(n)
    floor((3^n+3)*3/8) ;
end proc:
seq(A039300(n),n=0..30) ; # R. J. Mathar, Sep 28 2017

CoefficientList[Series[(1-x-3x^2)/((1-x)(1+x)(1-3x)),{x,0,30}],x] (* Vincenzo Librandi, Apr 21 2012 *)
Table[Floor((3^n+3)*3/8),{n,0,30}] (* Bruno Berselli, Apr 21 2012 *)
CoefficientList[Series[1/8 E^-x (-1 + 6 E^(2 x) + 3 E^(4 x)), {x, 0, 30}], x]*Table[k!, {k, 0, 30}] (* Stefano Spezia, Sep 04 2018 *)

{a(n) = if(n<0, 0, 3^n*3\8 + 1)}; /* Michael Somos,Mar 27 2005 */

{a(n) = if(n<1, n==0, 3*a(n-1) - 2 + n%2)}; /* Michael Somos, Mar 27 2005 */

[(3^(n+1) +6 -(-1)^n)/8 for n in (0..30)] # G. C. Greubel, Jul 14 2019

a(n) = floor(3*(3^n + 3)/8).
a(n) = A033113(n) + 1.
a(n) = (3^(n+1) + 6 + (-1)^(n+1))/8. - Lekraj Beedassy, Jan 07 2005
G.f.: (1 - x - 3*x^2)/((1 - x)*(1 + x)*(1 - 3*x)). - Michael Somos, Mar 27 2005
a(n) = 2*a(n-1) + 3*a(n-2) - 3 with n > 1, a(0) = 1, a(1) = 1. - Zerinvary Lajos, Dec 14 2008
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3). Vincenzo Librandi, Apr 21 2012
a(n) = A000224(3^n). - R. J. Mathar, Sep 28 2017
E.g.f.: (1/8)*exp(-x)*(-1+6*exp(2*x)+3*exp(4*x)). - Stefano Spezia, Sep 04 2018

A231219 T(n,k)=Number of (n+1)X(k+1) 0..2 arrays with no element unequal to a strict majority of its horizontal and vertical neighbors, with values 0..2 introduced in row major order.

Original entry on oeis.org

3, 4, 4, 7, 9, 7, 12, 22, 22, 12, 23, 59, 93, 59, 23, 44, 156, 408, 408, 156, 44, 87, 413, 1793, 2892, 1793, 413, 87, 172, 1098, 7844, 20027, 20027, 7844, 1098, 172, 343, 2919, 34609, 139438, 226764, 139438, 34609, 2919, 343, 684, 7760, 152421, 969461

Offset: 1

R. H. Hardin, Nov 05 2013

Table starts
...3.....4.......7........12..........23............44.............87
...4.....9......22........59.........156...........413...........1098
...7....22......93.......408........1793..........7844..........34609
..12....59.....408......2892.......20027........139438.........969461
..23...156....1793.....20027......226764.......2534951.......28439115
..44...413....7844....139438.....2534951......45593903......820418528
..87..1098...34609....969461....28439115.....820418528....23748656906
.172..2919..152421...6745110...318236849...14743946094...685733582035
.343..7760..672446..46938804..3565691309..265057746273.19812622781057
.684.20633.2965705.326645650.39935313475.4764850607558

			Some solutions for n=4 k=4
..0..0..0..1..1....0..0..0..0..0....0..0..0..0..0....0..0..1..1..0
..0..0..0..1..1....1..1..1..1..1....1..1..1..2..2....0..0..1..1..0
..0..0..0..2..2....1..0..0..0..1....1..1..1..2..2....0..0..1..1..0
..0..0..0..2..2....1..0..0..0..1....1..1..1..2..2....0..0..1..1..0
..2..2..2..2..2....1..1..1..1..1....1..1..1..2..2....0..0..1..1..0

R. H. Hardin, Table of n, a(n) for n = 1..127

Column 1 is A023105(n+2)

Empirical for column k:
k=1: a(n) = 2*a(n-1) +a(n-2) -2*a(n-3)
k=2: a(n) = 3*a(n-1) -a(n-2) +a(n-3) -2*a(n-4)
k=3: [order 19]
k=4: [order 68]

A000993 Number of distinct quadratic residues mod 10^n; also number of distinct n-digit endings of base-10 squares.

Original entry on oeis.org

1, 6, 22, 159, 1044, 9121, 78132, 748719, 7161484, 70800861, 699869892, 6978353179, 69580078524, 695292156201, 6947835288052, 69465637212039, 694529215501164, 6944974263529141, 69446563720728612, 694457689921141299, 6944497426351013404

Offset: 0

N. J. A. Sloane

			Any square ends with one of 0, 1, 4, 5, 6, 9, so a(1) = 6.
A square may end with 22 different two-digit combinations: 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96. E.g., no number ending with 14 can be square, etc. See also A075821, A075823.
The finite sequence A122986 has a(3) = 159 terms. - _Reinhard Zumkeller_, Mar 21 2010

Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publ., 2nd Ed., NY, 1966, Chapter XV, 'On The Square', p. 139.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Shyam Sunder Gupta, Elegance of Squares, Cubes, and Higher Powers, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 2, 29-81.
Walter Penney, On the final digits of squares, Amer. Math. Monthly, 67 (1960), 1000-1002.
Index entries for sequences related to final digits of numbers
Index entries for linear recurrences with constant coefficients, signature (10,30,-300,-129,1290,100,-1000).

Cf. A036688, A023105, A039300-A039306, A075821, A075823.

[1] cat [(83 + 27*(-1)^n + 9*2^(1 + n) + (-1)^n*2^(2 + n) + 9*5^(2 + n) + (-1)^n*5^(2 + n) + 2^(1 + n)*5^(2 + n))/ 72: n in [0..20]]; // Vincenzo Librandi, Mar 29 2012

-(-6+38*z+241*z^2-594*z^3-1285*z^4+1600*z^5+1500*z^6)/((-1+z)*(5*z-1)*(2*z+1)*(2*z-1)*(5*z+1)*(10*z-1)*(z+1)); #  Bruno Salvy

a[n_] := (83 - 27*(-1)^n + 9*2^(n) - (-1)^n*2^(1 + n) + 9*5^(1 + n) - (-1)^n*5^(1 + n) + 2^(n)*5^(1 + n))/72; Table[ Floor[ a[n]], {n, 0, 20}]
(* Or *) a[0] = 1; a[1] = 6; a[2] = 22; a[3] = 159; a[4] = 1044; a[5] = 9121; a[6] = 78132; a[7] = 748719; a[8] = 7161484; a[n_] := 130 a[n - 2] - 3129 a[n - 4] + 13000 a[n - 6] - 10000 a[n - 8]; Table[ a[n], {n, 0, 20}]
(* Or *) CoefficientList[ Series[(1 - 4*x - 68*x^2 + 59*x^3 + 723*x^4 - 5*x^5 - 1700*x^6 - 500*x^7)/(1 - 10*x - 30*x^2 + 300*x^3 + 129*x^4 - 1290*x^5 - 100*x^6 + 1000*x^7), {x, 0, 20}], x] (* Robert G. Wilson v, Nov 27 2004 *)
LinearRecurrence[{10,30,-300,-129,1290,100,-1000},{1,6,22,159,1044,9121,78132,748719},20] (* Harvey P. Dale, Dec 17 2017 *)

print([(2 + 2**n // 6) * (1 + 5**(n+1) // 12) if n else 1 for n in range(21)]) # Nick Hobson, Mar 10 2024

a(n) = floor( (83 - (-1)^n*(27 + 2^(n+1) + 5^(n+1)) + 9*2^n + (9 + 2^n)*5^(n+1)) / 72 ).
a(n+8) = 130 a(n+6) - 3129 a(n+4) + 13000 a(n+2) - 10000 a(n) for n >= 1.
G.f.: (1 - 4*x - 68*x^2 + 59*x^3 + 723*x^4 - 5*x^5 - 1700*x^6 - 500*x^7)/(1 - 10*x - 30*x^2 + 300*x^3 + 129*x^4 - 1290*x^5 - 100*x^6 + 1000*x^7).

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

A005578 a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A000224 Number of squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A231396 T(n,k)=Number of (n+1)X(k+1) 0..2 arrays with no element unequal to a strict majority of its horizontal, diagonal and antidiagonal neighbors, with values 0..2 introduced in row major order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A231263 T(n,k)=Number of (n+1)X(k+1) 0..2 arrays with no element unequal to a strict majority of its horizontal and antidiagonal neighbors, with values 0..2 introduced in row major order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A039300 Number of distinct quadratic residues mod 3^n.

Views

Author

Keywords

Comments

References

Links

A005578 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)-1.