cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A002828 Least number of squares that add up to n.

Original entry on oeis.org

0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Lagrange's "Four Squares theorem" states that a(n) <= 4.
It is easy to show that this is also the least number of squares that add up to n^3.
a(n) is the number of iterations in f(...f(f(n))...) to reach 0, where f(n) = A262678(n) = n - A262689(n)^2. Allows computation of this sequence without Lagrange's theorem. - Antti Karttunen, Sep 09 2016
It is also easy to show that a(k^2*n) = a(n) for k > 0: Clearly a(k^2*n) <= a(n) but for all 4 cases of a(n) there is no k which would result in a(k^2*n) < a(n). - Peter Schorn, Sep 06 2021

References

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

Links

Crossrefs

Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.
Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.

Programs

  • Haskell
    a002828 0 = 0  -- confessedly  /= 1, as sum [] == 0
a002828 n | a010052 n == 1 = 1
          | a025426 n > 0 = 2 | a025427 n > 0 = 3 | otherwise = 4
-- Reinhard Zumkeller, Feb 26 2015
  • Maple
    with(transforms);
sq:=[seq(n^2, n=1..20)];
LAGRANGE(sq,4,120);
# alternative:
f:= proc(n) local F,x;
   if issqr(n) then return 1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return 2 fi;
   x:= n/4^floor(padic:-ordp(n,2)/2);
   if x mod 8 = 7 then 4 else 3 fi
end proc:
0, seq(f(n),n=1..200); # Robert Israel, Jun 14 2016
# next Maple program:
b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+(s-> `if`(s>n, 0, x*b(n-s, i)))(i^2))), x, 5), polynom)
    end:
a:= n-> ldegree(b(n, isqrt(n))):
seq(a(n), n=0..105);  # Alois P. Heinz, Oct 30 2021
  • Mathematica
    SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; Table[SquareCnt[n], {n, 150}] (* T. D. Noe, Apr 01 2011 *)
sc[n_]:=Module[{s=SquaresR[Range[4],n]},If[First[s]>0,1,Length[ First[ Split[ s]]]+1]]; Join[{0},Array[sc,110]] (* Harvey P. Dale, May 21 2014 *)
  • PARI
    istwo(n:int)=my(f);if(n<3,return(n>=0););f=factor(n>>valuation(n, 2)); for(i=1,#f[,1],if(bitand(f[i,2],1)==1&&bitand(f[i,1],3)==3, return(0)));1
isthree(n:int)=my(tmp=valuation(n,2));bitand(tmp,1)||bitand(n>>tmp,7)!=7
a(n)=if(isthree(n), if(issquare(n), !!n, 3-istwo(n)), 4) \\ Charles R Greathouse IV, Jul 19 2011, revised Mar 17 2022
  • Python
    from sympy import factorint
def A002828(n):
    if n == 0: return 0
    f = factorint(n).items()
    if not any(e&1 for p,e in f): return 1
    if all(p&3<3 or e&1^1 for p,e in f): return 2
    return 3+(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # Chai Wah Wu, Aug 01 2023
  • Python
    from sympy.core.power import isqrt
def A002828(n):
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        S = []
        r = isqrt(i)
        for j in range(1, r + 1):
            S.append(1 + dp[i - (j**2)])
        dp[i] = min(S)
    return dp[-1] # Darío Clavijo, Apr 21 2025
  • Scheme
    ;; The first one follows Charles R Greathouse IV's PARI-code above:
(define (A002828 n) (cond ((zero? n) n) ((= 1 (A010052 n)) 1) ((= 1 (A229062 n)) 2) (else (+ 3 (A072401 n)))))
(define (A229062 n) (- 1 (A000035 (A260728 n))))
;; We can also compute this without relying on Lagrange's theorem. The following recursion-formula should be used together with the second Scheme-implementation of A262689 given in the Program section that entry:
(definec (A002828 n) (if (zero? n) n (+ 1 (A002828 (- n (A000290 (A262689 n)))))))
;; Antti Karttunen, Sep 09 2016

Formula

From Antti Karttunen, Sep 09 2016: (Start)
a(0) = 0; and for n >= 1, if A010052(n) = 1 [when n is a square], a(n) = 1, otherwise, if A229062(n)=1, then a(n) = 2, otherwise a(n) = 3 + A072401(n). [After Charles R Greathouse IV's PARI program.]
a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
a(n) = A053610(n) - A062535(n).
(End)

Extensions

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

A276573 The infinite trunk of least squares beanstalk: The only infinite sequence such that a(0) = 0 and a(n-1) = a(n) - least number of squares (A002828) that sum to a(n).

Original entry on oeis.org

0, 3, 6, 8, 11, 15, 16, 18, 21, 24, 27, 30, 32, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 63, 64, 67, 70, 72, 75, 78, 80, 83, 85, 88, 90, 93, 96, 99, 102, 105, 108, 112, 115, 117, 120, 123, 126, 128, 131, 134, 136, 139, 143, 144, 147, 149, 152, 155, 158, 160, 162, 165, 168, 171, 173, 176, 179, 183, 186, 189, 192, 195
Offset: 0

Views

Author

Antti Karttunen, Sep 07 2016

Keywords

Links

Crossrefs

Cf. A002828, A005563, A255131, A260731, A260733, A262689, A276572, A276574, A276575 (first differences), A277016 (squares present), A277015 (their square roots), A277888 (primes), A278486 (numbers one more than a prime), A278265, A278487, A278488, A278491 (another subsequence), A278497, A278498, A278499, A278513, A278516, A278517, A278518, A278519, A278521, A278522.
Cf. A277890 & A277891 (number of even and odd terms in each range. The latter seem to be slightly more numerous), A277889.
Positions of nonzero terms in A278515.
Subsequence of A278489, no common terms with A278490.
Cf. also A179016, A259934, A276583, A276613, A276623 for similar constructions.

Programs

Formula

a(n) = A276574(A276572(n)).
Other identities and observations. For all n >= 0:
A260731(a(n)) = n.
a(A260733(n+1)) = A005563(n).
A278517(n) <= a(n) <= A278519(n).
A010873(a(n)) = A278499(n). [Terms reduced modulo 4.]
A010877(a(n)) = A278488(n). [modulo 8.]
A046523(a(n)) = A278497(n). [Least number with the same prime signature.]
A008683(a(n)) = A278513(n).
A065338(a(n)) = A278498(n).
A278509(a(n)) = A278265(n).
A278216(a(n)) = A278516(n). [Number of children the n-th node of the trunk has.]

Extensions

Definition clarified and more identities added to the Formula section by Antti Karttunen, Nov 28 2016

A255131 n minus the least number of squares that add up to n: a(n) = n - A002828(n).

Original entry on oeis.org

0, 0, 0, 0, 3, 3, 3, 3, 6, 8, 8, 8, 9, 11, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 21, 24, 24, 24, 24, 27, 27, 27, 30, 30, 32, 32, 35, 35, 35, 35, 38, 39, 39, 40, 41, 43, 43, 43, 45, 48, 48, 48, 50, 51, 51, 51, 53, 54, 56, 56, 56, 59, 59, 59, 63, 63, 63, 64, 66, 66, 67, 67, 70, 71, 72, 72, 73, 74, 75, 75, 78, 80, 80, 80, 81
Offset: 0

Views

Author

Antti Karttunen, Feb 24 2015

Keywords

Comments

The associated beanstalk-sequence starts from a(0) as: 0, 3, 6, 8, 11, 15, 16, 18, 21, ... (A276573).

Examples

			a(0) = 0, because no squares are needed for an empty sum, and 0 - 0 = 0.
a(3) = 0, because 3 cannot be represented as a sum of less than three squares (1+1+1), and 3 - 3 = 0.
a(4) = 3, because 4 can be represented as a sum of just one square (namely 4 itself), and 4 - 1 = 3.

Links

Crossrefs

Subsequence: A005563.
Cf. A000290, A002828, A062535, A260731, A260732, A260733, A260734, A262689, A276573.
Cf. also A011371, A236840, A260740.

Programs

  • Maple
    f:= proc(n) local F, x;
   if issqr(n) then return n-1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return n-2 fi;
   x:= n/4^floor(padic:-ordp(n, 2)/2);
   if x mod 8 = 7 then n-4 else n-3 fi
end proc:
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Mar 27 2018
  • Mathematica
    {0}~Join~Table[n - (If[First@ # > 0, 1, Length[First@ Split@ #] + 1] &@ SquaresR[Range@ 4, n]), {n, 84}] (* Michael De Vlieger, Sep 08 2016, after Harvey P. Dale at A002828 *)

Formula

a(n) = n - A002828(n).
a(n) = A260740(n) + A062535(n).

A276574 The infinite trunk of least squares beanstalk with reversed subsections.

Original entry on oeis.org

0, 3, 8, 6, 15, 11, 24, 21, 18, 16, 35, 32, 30, 27, 48, 45, 43, 40, 38, 63, 59, 56, 53, 51, 80, 78, 75, 72, 70, 67, 64, 99, 96, 93, 90, 88, 85, 83, 120, 117, 115, 112, 108, 105, 102, 143, 139, 136, 134, 131, 128, 126, 123, 168, 165, 162, 160, 158, 155, 152, 149, 147, 144, 195, 192, 189, 186, 183, 179, 176, 173, 171
Offset: 0

Views

Author

Antti Karttunen, Sep 07 2016

Keywords

Examples

			This can be viewed as an irregular table, where after 0, each row has A260734(n) = 1, 2, 2, 4, 4, 5, 5, 7, ... terms:
0;
3;
8, 6;
15, 11;
24, 21, 18, 16;
35, 32, 30, 27;
48, 45, 43, 40, 38;
63, 59, 56, 53, 51;
80, 78, 75, 72, 70, 67, 64;
99, 96, 93, 90, 88, 85, 83;
120, 117, 115, 112, 108, 105, 102;
...
Each row begins with (n^2)-1 (see A005563), and each successive term is obtained by subtracting A002828(k) from the previous term k, until ((n-1)^2)-1 would be encountered, which is not listed second time (as it already occurs as the first term of the previous row), but instead, the current row is finished and the next row is started with the term ((n+1)^2)-1.

Links

Crossrefs

Cf. A005563 (left edge), A277023 (right edge).
Cf. A000196, A000290, A002828, A010052, A255131, A260734, A262689, A276572.
Used to construct A276573.
Cf. A277015 (tells which rows end with squares, listed in A277016).

Programs

  • Scheme
    (definec (A276574 n) (cond ((zero? n) n) ((= 1 n) 3) (else (let ((maybe_next (A255131 (A276574 (- n 1))))) (if (zero? (A010052 (+ 1 maybe_next))) maybe_next (+ -1 (A000290 (+ 2 (A000196 (+ 1 maybe_next))))))))))

Formula

a(0) = 0; a(1) = 3; for n > 1, let k = A255131(a(n-1)). If k+1 is not a square, then a(n) = k, otherwise a(n) = A000290(2+A000196(k+1)) - 1.

Extensions

Example section added and the formula rewritten to a simpler form (which is now correct) - Antti Karttunen, Oct 16 2016

A262690 a(n) = largest square k <= n such that A002828(n-k) = A002828(n)-1.

Original entry on oeis.org

0, 1, 1, 1, 4, 4, 4, 4, 4, 9, 9, 9, 4, 9, 9, 9, 16, 16, 9, 9, 16, 16, 9, 9, 16, 25, 25, 25, 25, 25, 25, 25, 16, 25, 25, 25, 36, 36, 36, 36, 36, 25, 25, 25, 36, 36, 36, 36, 16, 49, 49, 49, 36, 49, 49, 49, 36, 49, 49, 49, 49, 36, 49, 49, 64, 64, 64, 49, 64, 64, 36, 49, 36, 64, 49, 49, 36, 64, 49, 49, 64, 81, 81, 81, 64, 81, 81, 81, 36, 64, 81, 81, 81, 64, 81, 81, 64, 81, 49, 81, 100
Offset: 0

Views

Author

Antti Karttunen, Oct 03 2015

Keywords

Links

Crossrefs

Cf. A000290, A002828, A262689, A262678.
Cf. also A048760.

Programs

Formula

a(n) = A000290(A262689(n)).
Other identities. For all n >= 0:
A262678(n) = n - a(n).

A262678 a(n) = n - A262690(n), where A262690(n) = largest square k <= n such that A002828(n-k) = A002828(n)-1.

Original entry on oeis.org

0, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, 2, 8, 4, 5, 6, 0, 1, 9, 10, 4, 5, 13, 14, 8, 0, 1, 2, 3, 4, 5, 6, 16, 8, 9, 10, 0, 1, 2, 3, 4, 16, 17, 18, 8, 9, 10, 11, 32, 0, 1, 2, 16, 4, 5, 6, 20, 8, 9, 10, 11, 25, 13, 14, 0, 1, 2, 18, 4, 5, 34, 22, 36, 9, 25, 26, 40, 13, 29, 30, 16, 0, 1, 2, 20, 4, 5, 6, 52, 25, 9, 10, 11, 29, 13, 14, 32, 16, 49, 18, 0
Offset: 0

Views

Author

Antti Karttunen, Oct 03 2015

Keywords

Links

Crossrefs

Cf. A002828, A262689, A262690.
Cf. also A053186.

Programs

Formula

a(n) = n - A262690(n).
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.