A172151 -id:A172151 - cp's OEIS frontend

A000037 Numbers that are not squares (or, the nonsquares).

2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

Offset: 1

N. J. A. Sloane, Simon Plouffe

Note the remarkable formula for the n-th term (see the FORMULA section)!
These are the natural numbers with an even number of divisors. The number of divisors is odd for the complementary sequence, the squares (sequence A000290) and the numbers for which the number of divisors is divisible by 3 is sequence A059269. - Ola Veshta (olaveshta(AT)my-deja.com), Apr 04 2001
a(n) is the largest integer m not equal to n such that n = (floor(n^2/m) + m)/2. - Alexander R. Povolotsky, Feb 10 2008
Union of A007969 and A007970; A007968(a(n)) > 0. - Reinhard Zumkeller, Jun 18 2011
Terms of even numbered rows in the triangle A199332. - Reinhard Zumkeller, Nov 23 2011
If a(n) and a(n+1) are of the same parity then (a(n)+a(n+1))/2 is a square. - Zak Seidov, Aug 13 2012
Theaetetus of Athens proved the irrationality of the square roots of these numbers in the 4th century BC. - Charles R Greathouse IV, Apr 18 2013
4*a(n) are the even members of A079896, the discriminants of indefinite binary quadratic forms. - Wolfdieter Lang, Jun 14 2013

			For example note that the squares 0, 1, 4, 9, 16 are not included.

Titu Andreescu, Dorin Andrica, and Zuming Feng, 104 Number Theory Problems, Birkhäuser, 2006, 58-60.
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).

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 9900 terms from N. J. A. Sloane)
E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
A. J. dos Reis and D. M. Silberger, Generating nonpowers by formula, Math. Mag., 63 (1990), 53-55.
Bakir Farhi, An explicit formula generating the non-Fibonacci numbers, arXiv:1105.1127 [math.NT], May 05 2011.
S. R. Finch, Class number theory
Steven R. Finch, Class number theory [Cached copy, with permission of the author]
Henry W. Gould, Letters to N. J. A. Sloane, Oct 1973 and Jan 1974.
S. Kaji, T. Maeno, K. Nuida, and Y. Numata, Polynomial Expressions of Carries in p-ary Arithmetics, arXiv preprint arXiv:1506.02742 [math.CO], 2015-2016.
J. Lambek and L. Moser, Inverse and complementary sequences of natural numbers, Amer. Math. Monthly, 61 (1954), 454-458. doi 10.2307/2308078, see example 4 (includes the formula). [Nicolas Normand (Nicolas.Normand(AT)polytech.univ-nantes.fr), Nov 24 2009]
R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.
Cristinel Mortici, Remarks on Complementary Sequences, Fibonacci Quart. 48 (2010), no. 4, 343-347.
R. D. Nelson, Sequences which omit powers, The Mathematical Gazette, Number 461, 1988, pages 208-211.
M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 2002), 559-564.
Rosetta Code, Sequence of non-squares
J. Scholes, 27th Putnam 1966 Prob. A4
Aaron Snook, Augmented Integer Linear Recurrences, 2012. - From _N. J. A. Sloane_, Dec 19 2012
Eric Weisstein's World of Mathematics, Square Number
Eric Weisstein's World of Mathematics, Continued Fraction

Cf. A007412, A000005, A000290, A059269, A134986, A087153, A172151, A000196, A049068 (subsequence).
Cf. A242401 (subsequence).
Cf. A086849 (partial sums), A048395.

a000037 n = n + a000196 (n + a000196 n)
-- Reinhard Zumkeller, Nov 23 2011

[n : n in [1..1000] | not IsSquare(n) ];

at:=0; for n in [1..10000] do if not IsSquare(n) then at:=at+1; print at, n; end if; end for;

Maple
```
A000037 := n->n+floor(1/2+sqrt(n));
```

a[n_] := (n + Floor[Sqrt[n + Floor[Sqrt[n]]]]); Table[a[n], {n, 71}] (* Robert G. Wilson v, Sep 24 2004 *)
With[{upto=100},Complement[Range[upto],Range[Floor[Sqrt[upto]]]^2]] (* Harvey P. Dale, Dec 02 2011 *)
a[ n_] :=  If[ n < 0, 0, n + Round @ Sqrt @ n]; (* Michael Somos, May 28 2014 *)

A000037(n):=n + floor(1/2 + sqrt(n))$ makelist(A000037(n),n,1,50); /* Martin Ettl, Nov 15 2012 */

{a(n) = if( n<0, 0, n + (1 + sqrtint(4*n)) \ 2)};

from math import isqrt
def A000037(n): return n+isqrt(n+isqrt(n)) # Chai Wah Wu, Mar 31 2022

from math import isqrt
def A000037(n): return n+(k:=isqrt(n))+int(n>=k*(k+1)+1) # Chai Wah Wu, Jun 17 2024

a(n) = n + floor(1/2 + sqrt(n)).
a(n) = n + floor(sqrt( n + floor(sqrt n))).
A010052(a(n)) = 0. - Reinhard Zumkeller, Jan 26 2010
A173517(a(n)) = n; a(n)^2 = A030140(n). - Reinhard Zumkeller, Feb 20 2010
a(n) = A000194(n) + n. - Jaroslav Krizek, Jun 14 2009
a(A002061(n)) = a(n^2-n+1) = A002522(n) = n^2 + 1. - Jaroslav Krizek, Jun 21 2009

Edited by Charles R Greathouse IV, Oct 30 2009

A025426 Number of partitions of n into 2 nonzero squares.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0

Offset: 0

David W. Wilson

For records see A007511, A048610, A016032. - R. J. Mathar, Feb 26 2008

Robin Jones, Table of n, a(n) for n = 0..20000 (Terms 0..10000 from Reinhard Zumkeller).
Vaclav Kotesovec, Graph - the asymptotic ratio (10^8 terms)
Index entries for sequences related to sums of squares

Cf. A000161 (2 nonnegative squares), A063725 (order matters), A025427 (3 nonzero squares).
Cf. A172151, A004526. - Reinhard Zumkeller, Jan 26 2010
Column k=2 of A243148.

a025426 n = sum $ map (a010052 . (n -)) $
                      takeWhile (<= n `div` 2) $ tail a000290_list
a025426_list = map a025426 [0..]
-- Reinhard Zumkeller, Aug 16 2011

A025426 := proc(n)
    local a,x;
    a := 0 ;
    for x from 1 do
        if 2*x^2 > n then
            return a;
        end if;
        if issqr(n-x^2) then
            a := a+1 ;
        end if;
    end do:
end proc: # R. J. Mathar, Sep 15 2015

m[n_] := m[n] = SquaresR[2, n]/4; a[0] = 0; a[n_] := If[ EvenQ[ m[n] ], m[n]/2, (m[n] - (-1)^IntegerExponent[n, 2])/2]; Table[ a[n], {n, 0, 107}] (* Jean-François Alcover, Jan 31 2012, after Max Alekseyev *)
nmax = 107; sq = Range[Sqrt[nmax]]^2;
Table[Length[Select[IntegerPartitions[n, All, sq], Length[#] == 2 &]], {n, 0, nmax}] (* Robert Price, Aug 17 2020 *)

a(n)={my(v=valuation(n,2),f=factor(n>>v),t=1);for(i=1,#f[,1],if(f[i,1]%4==1,t*=f[i,2]+1,if(f[i,2]%2,return(0))));if(t%2,t-(-1)^v,t)/2;} \\ Charles R Greathouse IV, Jan 31 2012

from math import prod
from sympy import factorint
def A025426(n): return ((m:=prod(1 if p==2 else (e+1 if p&3==1 else (e+1)&1) for p, e in factorint(n).items()))+((((~n & n-1).bit_length()&1)<<1)-1 if m&1 else 0))>>1 # Chai Wah Wu, Jul 07 2022

Let m = A004018(n)/4. If m is even then a(n) = m/2, otherwise a(n) = (m - (-1)^A007814(n))/2. - Max Alekseyev, Mar 09 2009, Mar 14 2009
a(A018825(n)) = 0; a(A000404(n)) > 0; a(A025284(n)) = 1; a(A007692(n)) > 1. - Reinhard Zumkeller, Aug 16 2011
a(A000578(n)) = A084888(n). - Reinhard Zumkeller, Jul 18 2012
a(n) = Sum_{i=1..floor(n/2)} A010052(i) * A010052(n-i). - Wesley Ivan Hurt, Apr 19 2019
a(n) = [x^n y^2] Product_{k>=1} 1/(1 - y*x^(k^2)). - Ilya Gutkovskiy, Apr 19 2019
Conjecture: Sum_{k=1..n} a(k) ~ n*Pi/8. - Vaclav Kotesovec, Dec 28 2023

A087153 Number of partitions of n into nonsquares.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 3, 3, 5, 5, 8, 9, 13, 15, 20, 24, 30, 37, 47, 55, 71, 83, 103, 123, 151, 178, 218, 257, 310, 366, 440, 515, 617, 722, 857, 1003, 1184, 1380, 1625, 1889, 2214, 2570, 3000, 3472, 4042, 4669, 5414, 6244, 7221, 8303, 9583, 10998, 12655, 14502

Offset: 0

Reinhard Zumkeller, Aug 21 2003

nonn

Also, number of partitions of n where there are fewer than k parts equal to k for all k. - Jon Perry and Vladeta Jovovic, Aug 04 2004. E.g. a(8)=5 because we have 8=6+2=5+3=4+4=3+3+2.
Convolution of A276516 and A000041. - Vaclav Kotesovec, Dec 30 2016
From Gus Wiseman, Apr 02 2019: (Start)
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). The Heinz numbers of the integer partitions described in Perry and Jovovic's comment are given by A325128, while the Heinz numbers of the integer partitions described in the name are given by A325129. In the former case, the first 10 terms count the following integer partitions:
  ()  (2)  (3)  (4)  (5)   (6)   (7)   (8)    (9)
                     (32)  (33)  (43)  (44)   (54)
                           (42)  (52)  (53)   (63)
                                       (62)   (72)
                                       (332)  (432)
while in the latter case they count the following:
  ()  (2)  (3)  (22)  (5)   (6)    (7)    (8)     (63)
                      (32)  (33)   (52)   (53)    (72)
                            (222)  (322)  (62)    (333)
                                          (332)   (522)
                                          (2222)  (3222)
(End)

			n=7: 2+5 = 2+2+3 = 7: a(7)=3;
n=8: 2+6 = 2+2+2+2 = 2+3+3 = 3+5 = 8: a(8)=5;
n=9: 2+7 = 2+2+5 = 2+2+2+3 = 3+3+3 = 3+6: a(9)=5.

G. E. Andrews, K. Eriksson, Integer Partitions, Cambridge Univ. Press, 2004. See page 48.

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Daniel I. A. Cohen, PIE-sums: a combinatorial tool for partition theory. J. Combin. Theory Ser. A 31 (1981), no. 3, 223--236. MR0635367 (82m:10026). See Cor. 5. - _N. J. A. Sloane_, Mar 27 2012
James A. Sellers, Partitions Excluding Specific Polygonal Numbers As Parts, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.

Cf. A087154, A001156, A000009, A000037, A052335 (<=k parts of k).
Cf. A115584, A172151, A225044, A264393, A276516.
Cf. A033461, A114639, A117144, A276429, A324572, A324588, A325128, A325129.

a087153 = p a000037_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Apr 25 2013

g:=product((1-x^(i^2))/(1-x^i),i=1..70):gser:=series(g,x=0,60):seq(coeff(gser,x^n),n=1..53); # Emeric Deutsch, Feb 09 2006

nn=54; CoefficientList[ Series[ Product[ Sum[x^(i*j), {j, 0, i - 1}], {i, 1, nn}], {x, 0, nn}], x] (* Robert G. Wilson v, Aug 05 2004 *)
nmax = 100; CoefficientList[Series[Product[(1 - x^(k^2))/(1 - x^k), {k, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Dec 29 2016 *)

first(n)=my(x='x+O('x^(n+1))); Vec(prod(m=1,sqrtint(n), (1-x^m^2)/(1-x^m))*prod(m=sqrtint(n)+1,n,1/(1-x^m))) \\ Charles R Greathouse IV, Aug 28 2016

G.f.: Product_{m>0} (1-x^(m^2))/(1-x^m). - Vladeta Jovovic, Aug 21 2003
a(n) = (1/n)*Sum_{k=1..n} (A000203(k)-A035316(k))*a(n-k), a(0)=1. - Vladeta Jovovic, Aug 21 2003
G.f.: Product_{i>=1} (Sum_{j=0..i-1} x^(i*j)). - Jon Perry, Jul 26 2004
a(n) ~ exp(Pi*sqrt(2*n/3) - 3^(1/4) * Zeta(3/2) * n^(1/4) / 2^(3/4) - 3*Zeta(3/2)^2/(32*Pi)) * sqrt(Pi) / (2^(3/4) * 3^(1/4) * n^(3/4)). - Vaclav Kotesovec, Dec 30 2016

Zeroth term added by Franklin T. Adams-Watters, Jan 25 2010

A337853 a(n) is the number of partitions of n as the sum of two Niven numbers.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 3, 2, 4, 3, 3, 4, 3, 3, 5, 3, 4, 5, 4, 4, 7, 4, 5, 6, 5, 3, 7, 4, 4, 6, 4, 2, 7, 3, 4, 5, 4, 3, 7, 3, 4, 5, 4, 3, 8, 3, 4, 6, 3, 3, 6, 2, 5, 6, 5, 3, 8, 4, 4, 6

Offset: 0

Marius A. Burtea, Sep 26 2020

a(n) >= 1 for n >= 2 ?.

For n <= 200000, a(n) = 1 only for n = 2, 3, 299, (2 = 1 + 1, 3 = 1 + 2, 299 = 1 + 288) and a(n) = 2 only for n in {4, 5, 35, 59, 79, 95, 97, 149, 169, 179, 389}.

			0 and 1 cannot be decomposed as the sum of two Niven numbers, so a(0) = a(1) = 0.
4 = 1 + 3 = 2 + 2 and 1, 2, 3 are in A005349, so a(4) = 2.
15 = 3 + 12 = 5 + 10 = 6 + 9 = 7 + 8 and 3, 5, 6, 7, 8, 9, 10, 12 are in A005349, so a(15) = 4.

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Cf. A005349, A116357, A172151, A172398, A180149, A280829, A319468, A302479, A319395, A337854.

niven:=func; [#RestrictedPartitions(n,2,{k: k in [1..n-1] | niven(k)}): n in [0..100]];

m = 100; nivens = Select[Range[m], Divisible[#, Plus @@ IntegerDigits[#]] &]; a[n_] := Length[IntegerPartitions[n, {2}, nivens]]; Array[a, m, 0] (* Amiram Eldar, Sep 27 2020 *)

cp's OEIS Frontend

A000037 Numbers that are not squares (or, the nonsquares).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

Python

Python

Formula

Extensions

A025426 Number of partitions of n into 2 nonzero squares.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A087153 Number of partitions of n into nonsquares.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A337853 a(n) is the number of partitions of n as the sum of two Niven numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A172152 Records for number of partitions of n into two nonsquares.

Views

Author

Keywords

Comments

A172153 Where records occur for number of partitions of n into two nonsquares.

Views

Author

Keywords

Comments