A061786 -id:A061786 - cp's OEIS frontend

A061790 a(n) = A000217(n) - A061786(n).

0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 5, 6, 8, 11, 12, 14, 18, 20, 25, 27, 31, 35, 42, 46, 50, 55, 61, 67, 74, 78, 87, 94, 101, 111, 118, 124, 133, 143, 153, 159, 172, 181, 193, 206, 214, 227, 240, 251, 265, 277, 290, 303, 322, 337, 350, 363, 378, 392, 410, 421, 440, 461

Offset: 1

Labos Elemer, Jun 22 2001

nonn

If the {s+t} sums are generated by addition 2 terms of an S set consisting of n different entries, then at least 1 and at most n(n+1)/2=A000217(n) distinct values can be obtained. The set of first n squares gives results falling between these two extremes.

Original name: "Number of sums i^2 + j^2 that occur more than once for 1 <= i <= j <= n." This was incorrect because sums that occur more than twice are overcounted. - Robert Israel, Jun 26 2025

			S={1,4,9,...,100,121} provides 61 different sums of two (not necessarily different) squares: {2,5,8,..,202,221,242}. Only 5 of these sums arise more than once:
   50 = 1 +  49 = 25 +  25;
   65 = 1 +  64 = 16 +  49;
   85 = 4 +  81 = 36 +  49;
  125 = 4 + 121 = 25 + 100;
  130 = 9 + 121 = 49 +  81.
Therefore a(11) = (12*11/2) - 61 = 5.

Cf. A000217, A385352.

N:= 100: # for a(1) .. a(N)
V:= Vector(2*N^2, datatype=integer[4]):
R:= Vector(N):
count:= 0:
for n from 1 to N do
  for i from 1 to n do
    t:= i^2 + n^2;
    V[t]:= V[t]+1;
    if V[t] = 1 then count:= count+1 fi;
  od;
  R[n]:= n*(n+1)/2 - count
od:
convert(R,list); # Robert Israel, Jun 26 2025

f[x_] := x^2 t0=Table[Length[Union[Flatten[Table[f[u]+f[w], {w, 1, m}, {u, 1, m}]]]], {m, 1, 75}] t1=Table[(w*(w+1)/2)-Part[t0, w], {w, a, b}]

def A061790(n): return (n*(n+1)>>1)-len({i**2+j**2 for i in range(1,n+1) for j in range(1,i+1)}) # Chai Wah Wu, Jun 27 2025

Definition corrected by Robert Israel, Jun 26 2025

A126256 Number of distinct terms in rows 0 through n of Pascal's triangle.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 9, 12, 16, 20, 24, 29, 35, 41, 48, 53, 60, 68, 77, 86, 95, 103, 114, 125, 137, 149, 162, 175, 188, 202, 217, 232, 248, 264, 281, 297, 314, 332, 351, 370, 390, 410, 431, 452, 474, 495, 518, 541, 565, 589, 614, 639, 665, 691, 718, 744, 770, 798

Offset: 0

Nick Hobson, Dec 24 2006

An easy upper bound is 1 + floor(n^2/4) = A033638(n).

First differences are in A126257.

			There are 9 distinct terms in rows 0 through 6 of Pascal's triangle (1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1); hence a(6)=9.

Nick Hobson, Table of n, a(n) for n = 0..1000
Nick Hobson, Python program for this sequence

Cf. A007318, A027424, A061786, A126254, A126255, A126257.
Cf. A199425.
Cf. A258318.

-- import Data.List.Ordered (insertSet)
a126256 n = a126256_list !! n
a126256_list = f a007318_tabl [] where
   f (xs:xss) zs = g xs zs where
     g []     ys = length ys : f xss ys
     g (x:xs) ys = g xs (insertSet x ys)
-- Reinhard Zumkeller, May 26 2015, Nov 09 2011

seq(nops(`union`(seq({seq(binomial(n,k),k=0..n)},n=0..m))),m=0..57); # Emeric Deutsch, Aug 26 2007

Table[Length[Union[Flatten[Table[Binomial[n,k],{n,0,x},{k,0,n}]]]],{x,0,60}] (* Harvey P. Dale, Sep 10 2022 *)

lim=57; z=listcreate(1+lim^2\4); for(n = 0, lim, for(r=1, n\2, s=Str(binomial(n, r)); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); print1(1+#z, ", "))

def A126256(n):
    s, c = (1,), {1}
    for i in range(n):
        s = (1,)+tuple(s[j]+s[j+1] for j in range(len(s)-1)) + (1,)
        c.update(set(s))
    return len(c) # Chai Wah Wu, Oct 17 2023

A126254 Number of distinct terms i^j for 1 <= i,j <= n.

Original entry on oeis.org

1, 3, 7, 11, 19, 28, 40, 50, 60, 76, 96, 115, 139, 163, 189, 207, 239, 270, 306, 340, 378, 417, 461, 503, 539, 585, 621, 670, 726, 779, 839, 881, 941, 1003, 1067, 1113, 1185, 1254, 1326, 1397, 1477, 1553, 1637, 1717, 1799, 1884, 1976, 2063, 2135, 2225

Offset: 1

Nick Hobson, Dec 24 2006

An easy upper bound is n(n-1)+1 = A002061(n).

			a(4) = 11, as there are 11 distinct terms in 1^1=1, 1^2=1, 1^3=1, 1^4=1, 2^1=2, 2^2=4, 2^3=8, 2^4=16, 3^1=3, 3^2=9, 3^3=27, 3^4=81, 4^1=4, 4^2=16, 4^3=64, 4^4=256.

Nick Hobson and John Silberholz, Table of n, a(n) for n = 1..10000 [Terms 1 through 1000 were computed by N. Hobson; terms 1001 through 10000 by John Silberholz, Feb 23 2015]
John Silberholz, Combinatorial approach to calculate sequence

Cf. A027424, A061786, A126255, A126256, A126257.

seq(nops({seq(seq(i^j, i=1..n),j=1..n)}),n=1..100); # Robert Israel, Feb 23 2015

lim=50; z=listcreate(lim*(lim-1)+1); for(m=1, lim, for(i=1, m, x=factor(i); x[, 2]*=m; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); t=factor(m); for(j=1, m, x=t; x[, 2]=j*t[, 2]; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); print1(#z, ", "))

def A126254(n): return len({i**j for i in range(1,n+1) for j in range(1,n+1)}) # Chai Wah Wu, Oct 17 2023

A126254 <- function(limit) {  if (limit == 1) { return(1) } ; num.powers <- c(1, rep(0, limit-1)) ; handled <- c(T, rep(F, limit-1)) ; for (base in 2:ceiling(sqrt(limit))) { if (!handled[base]) { num.handle <- floor(log(limit, base)) ; handled[base^(1:num.handle)] <- T ; num.powers[base] <- length(unique(as.vector(outer(1:num.handle, 1:limit)))) }} ; num.powers[!handled] <- limit ; sum(num.powers) } ; A126254(50) # John Silberholz, Feb 23 2015

A126255 Number of distinct terms i^j for 2 <= i,j <= n.

Original entry on oeis.org

1, 4, 8, 15, 23, 34, 44, 54, 69, 88, 106, 129, 152, 177, 195, 226, 256, 291, 324, 361, 399, 442, 483, 519, 564, 600, 648, 703, 755, 814, 856, 915, 976, 1039, 1085, 1156, 1224, 1295, 1365, 1444, 1519, 1602, 1681, 1762, 1846, 1937, 2023, 2095, 2184, 2279

Offset: 2

Nick Hobson, Dec 24 2006

An easy upper bound is (n-1)^2 = A000290(n-1).

			a(4) = 8 as there are 8 distinct terms in 2^2=4, 2^3=8, 2^4=16, 3^2=9, 3^3=27, 3^4=81, 4^2=16, 4^3=64, 4^4=256.

Eric M. Schmidt, Table of n, a(n) for n = 2..10000
Project Euler, Problem 29: Distinct powers.

Cf. A027424, A061786, A126254, A126256, A126257.

SetAttributes[a, {Listable, NumericFunction}]
a[n_ /; n < 2] := "error"
a[2] := 1
a[n_Integer?IntegerQ /; n > 2] :=
 Length[DeleteDuplicates[
   Distribute[f[Range[2, n], Range[2, n]], List,
     f] /. {f ->
      Power}]](*By using Distribute instead of Outer I avoid having to use Flatten on Outer*)
a[Range[2, 100]]
(* Peter Cullen Burbery, Aug 15 2023 *)

lim=51; z=listcreate((lim-1)^2); for(m=2, lim, for(i=2, m, x=factor(i); x[, 2]*=m; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); t=factor(m); for(j=2, m, x=t; x[, 2]=j*t[, 2]; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); print1(#z, ", "))

def A126255(n): return len({i**j for i in range(2,n+1) for j in range(2,n+1)}) # Chai Wah Wu, Oct 17 2023

A374715 Number of distinct sums i^2 + j^2 + k^2 for 1<=i<=j<=k<=n.

Original entry on oeis.org

1, 4, 10, 20, 33, 51, 69, 94, 122, 157, 187, 233, 273, 316, 373, 432, 485, 558, 614, 694, 770, 849, 915, 1019, 1108, 1205, 1304, 1410, 1504, 1640, 1742, 1872, 1997, 2121, 2245, 2410, 2534, 2678, 2821, 2994, 3136, 3320, 3472, 3647, 3820, 3993, 4157, 4393, 4558, 4757, 4963, 5186, 5360, 5593

Offset: 1

Seiichi Manyama, Jul 17 2024

nonn

Cf. A061786, A374716.

a(n) = my(v=vector(3*n^2)); for(i=1, n, for(j=i, n, for(k=j, n, v[i^2+j^2+k^2]+=1))); sum(i=1, #v, v[i]>0);

def A374715(n): return len({i**2+j**2+k**2 for i in range(1,n+1) for j in range(i,n+1) for k in range(j,n+1)}) # Chai Wah Wu, Jul 17 2024

A374716 Number of distinct sums i^2 + j^2 + k^2 + l^2 for 1<=i<=j<=k<=l<=n.

Original entry on oeis.org

1, 5, 15, 34, 58, 93, 128, 175, 227, 289, 349, 429, 504, 592, 685, 791, 891, 1014, 1124, 1262, 1394, 1543, 1676, 1851, 2006, 2185, 2356, 2554, 2733, 2948, 3143, 3374, 3585, 3824, 4045, 4313, 4549, 4818, 5064, 5363, 5632, 5934, 6216, 6538, 6834, 7161, 7466, 7838, 8160, 8515, 8852, 9248, 9587, 9989

Offset: 1

Seiichi Manyama, Jul 17 2024

nonn

Cf. A061786, A374715.

a(n) = my(v=vector(4*n^2)); for(i=1, n, for(j=i, n, for(k=j, n, for(l=k, n, v[i^2+j^2+k^2+l^2]+=1)))); sum(i=1, #v, v[i]>0);

def A374716(n): return len({i**2+j**2+k**2+l**2 for i in range(1,n+1) for j in range(i,n+1) for k in range(j,n+1) for l in range(k,n+1)}) # Chai Wah Wu, Jul 17 2024

cp's OEIS Frontend

A061790 a(n) = A000217(n) - A061786(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A126256 Number of distinct terms in rows 0 through n of Pascal's triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

A126254 Number of distinct terms i^j for 1 <= i,j <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

R

A126255 Number of distinct terms i^j for 2 <= i,j <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A374715 Number of distinct sums i^2 + j^2 + k^2 for 1<=i<=j<=k<=n.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

A374716 Number of distinct sums i^2 + j^2 + k^2 + l^2 for 1<=i<=j<=k<=l<=n.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python