A027424 -id:A027424 - cp's OEIS frontend

A027428 Number of distinct products ij with 1 <= i < j <= n. (Number of terms appearing more than once in a 1-to-n multiplication table.)

0, 1, 3, 6, 10, 13, 19, 24, 31, 36, 46, 51, 63, 70, 78, 87, 103, 111, 129, 139, 150, 161, 183, 192, 210, 223, 239, 252, 280, 291, 321, 337, 354, 371, 390, 403, 439, 458, 478, 493, 533, 549, 591, 611, 631, 654, 700, 717, 752, 774, 800, 823, 875

Offset: 1

N. J. A. Sloane

Branden Aldridge, Table of n, a(n) for n = 1..20000 (terms 1..1000 from T. D. Noe).

Cf. A027424, A027427, A027430.

import Data.List (nub)
a027428 n = length $ nub [i*j | j <- [2..n], i <- [1..j-1]]
-- Reinhard Zumkeller, Jan 01 2012

f:=proc(n) local i,j,t1,t2; t1:={}; for i from 1 to n-1 do for j from i+1 to n do t1:={op(t1),i*j}; od: od: t1:=convert(t1,list); nops(t1); end;

a[n_] := Table[i*j, {i, 1, n-1}, {j, i+1, n}] // Flatten // Union // Length; Table[ a[n] , {n, 1, 53}] (* Jean-François Alcover, Jan 31 2013 *)

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

a(n) = A027427(n) - 1. - T. D. Noe, Jan 16 2007

A101301 The sum of the first n primes, minus n.

Original entry on oeis.org

1, 3, 7, 13, 23, 35, 51, 69, 91, 119, 149, 185, 225, 267, 313, 365, 423, 483, 549, 619, 691, 769, 851, 939, 1035, 1135, 1237, 1343, 1451, 1563, 1689, 1819, 1955, 2093, 2241, 2391, 2547, 2709, 2875, 3047, 3225, 3405, 3595, 3787, 3983, 4181, 4391, 4613, 4839

Offset: 1

Jorge Coveiro, Dec 22 2004

nonn

Also: a(n) = sum_{k=1..n} phi(prime(k)).
Partial sums of A006093. - Omar E. Pol, Oct 31 2013
Difference minus n, between the constant term prime(n) for a polynomial P(x) built from the first n primes took as coefficients and the value that such term should have in order to make P(x) divisible by (x-1). See links. - R. J. Cano, Jan 14 2014
Sum of all deficiencies of the first n primes. - Omar E. Pol, Feb 21 2014

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000
R. J. Cano, Additional information
R. J. Cano, PARI/GP code: alternative sequencer

Cf. A000010, A000040, A006093, A005867.

a101301 n = a101301_list !! (n-1)
a101301_list = scanl1 (+) a006093_list
-- Reinhard Zumkeller, May 01 2013

seq((sum(phi(ithprime(x)),k=1..n)),n=1..100);

f[n_]:=Plus@@Prime[Range[n]]-n; Table[f[n],{n,1,50}] (* Enrique Pérez Herrero, Jun 10 2012 *)

a(n)=my(s);forprime(p=2,prime(n),s+=p); s-n \\ Charles R Greathouse IV, Oct 31 2013

PARI
```
\\ See links.
```

a(n)=sum_{k=1..n} (prime(k)-1)
a(n)=A007504(n)-n. - Juri-Stepan Gerasimov, Nov 23 2009
A027424(A000040(n)) < a(n). - Charles R Greathouse IV, Apr 07 2021

Name simplified by Juri-Stepan Gerasimov, Nov 23 2009

A108407 Number of added unique known entries when going from the n X n to the (n+1) X (n+1) multiplication table.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 3, 3, 4, 0, 6, 0, 6, 6, 8, 0, 9, 0, 10, 9, 10, 0, 14, 9, 12, 12, 15, 0, 18, 0, 17, 15, 16, 15, 23, 0, 18, 18, 24, 0, 25, 0, 24, 24, 22, 0, 31, 18, 28, 24, 29, 0, 32, 24, 34, 27, 28, 0, 41, 0, 30, 35, 38, 29, 40, 0, 38, 33, 44, 0, 49, 0, 36, 41, 43, 32, 47, 0, 52

Offset: 1

Ralf Stephan, Jun 03 2005

nonn

			When going to 8 X 8, the added entries 8,16,24 are already known, so a(7)=3:
.1..2..3..4..5..6..7....8 *
....4..6..8.10.12.14...16 *
.......9.12.15.18.21...24 *
.........16.20.24.28...32
............25.30.35...40
...............36.42...48
..................49...56
.......................64

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Unique values of sequence are in A108408.

Cf. A027424 (total unique entries), A062854 (added unique unknown entries).

A108407 := proc(n)
    n+1-A062854(n+1) ;
end proc:
seq(A108407(n),n=1..40) ; # R. J. Mathar, Oct 02 2020

nmax = 100;
A062854 = Table[u = If[n == 1, {}, Union[u, n Range[n]]]; Length[u], {n, 1, nmax+1}] // Differences // Prepend[#, 1]&;
a[n_] := n + 1 - A062854[[n+1]];
Table[a[n], {n, 1, nmax}] (* Jean-François Alcover, Oct 02 2020 *)

from itertools import takewhile
from sympy import divisors
def A108407(n): return n+1-sum(1 for i in range(1,n+2) if all(d<=i for d in takewhile(lambda d:d<=n,divisors((n+1)*i)))) # Chai Wah Wu, Oct 13 2023

For prime p, a(p-1) = 0.

a(n) = n+1 - A062854(n+1).

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

A225246 T(n,k)=Number of distinct values of the sum of n products of a 0..k-1 and a 0..k integer.

Original entry on oeis.org

1, 3, 1, 6, 5, 1, 9, 12, 7, 1, 14, 22, 18, 9, 1, 18, 36, 34, 24, 11, 1, 25, 53, 56, 46, 30, 13, 1, 30, 74, 83, 76, 58, 36, 15, 1, 36, 98, 116, 113, 96, 70, 42, 17, 1, 42, 126, 154, 158, 143, 116, 82, 48, 19, 1, 53, 158, 198, 210, 200, 173, 136, 94, 54, 21, 1, 59, 193, 248, 270, 266

Offset: 1

R. H. Hardin May 04 2013

Table starts
.1..3..6...9..14..18..25..30..36..42...53...59...72...80...89...97..114..123
.1..5.12..22..36..53..74..98.126.158..193..231..274..320..369..423..481..542
.1..7.18..34..56..83.116.154.198.248..303..363..430..502..579..663..753..848
.1..9.24..46..76.113.158.210.270.338..413..495..586..684..789..903.1025.1154
.1.11.30..58..96.143.200.266.342.428..523..627..742..866..999.1143.1297.1460
.1.13.36..70.116.173.242.322.414.518..633..759..898.1048.1209.1383.1569.1766
.1.15.42..82.136.203.284.378.486.608..743..891.1054.1230.1419.1623.1841.2072
.1.17.48..94.156.233.326.434.558.698..853.1023.1210.1412.1629.1863.2113.2378
.1.19.54.106.176.263.368.490.630.788..963.1155.1366.1594.1839.2103.2385.2684
.1.21.60.118.196.293.410.546.702.878.1073.1287.1522.1776.2049.2343.2657.2990

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

Row 1 is A027424

Empirical: column k is n*k*(k-1) - A225249(k) for large n (n>2 suffices through at least k=555)

A263995 Cardinality of the union of the set of sums and the set of products made from pairs of integers from {1..n}.

Original entry on oeis.org

2, 4, 7, 11, 15, 20, 27, 32, 39, 46, 56, 63, 75, 83, 93, 102, 118, 127, 146, 156, 169, 182, 204, 215, 231, 245, 261, 274, 302, 315, 346, 361, 379, 398, 418, 432, 469, 489, 510, 527, 567, 585, 627, 647, 669, 693, 739, 756, 788, 810, 838, 862, 914, 937

Offset: 1

Hugo Pfoertner, Nov 15 2015

nonn

The November 2015 - Feb 2016 round of Al Zimmermann's Programming Contests asks for sets of positive integers (instead of {1..n}) minimizing the cardinality of the union of the sum-set and the product-set for set sizes 40, 80, ..., 1000. [corrected by Al Zimmermann, Nov 24 2015]

			a(3)=7 because the union of the set of sums {1+1, 1+2, 1+3, 2+2, 2+3, 3+3} and the set of products {1*1, 1*2, 1*3, 2*2, 2*3, 3*3} = {2,3,4,5,6} U {1,2,3,4,6,9} = {1,2,3,4,5,6,9} has cardinality 7.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag New York, 2004. Problem F18.

Hugo Pfoertner, Table of n, a(n) for n = 1..10000
P. Erdős and E. Szemeredi, On sums and products of integers, Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 213-218. DOI:10.1007/978-3-0348-5438-2_19
Al Zimmermann's Programming Contests, Sums and Products I, Nov 2015 - Feb 2016.

Cf. A027424, A108954, A263996.

a(n) = {my(v = [1..n]); v = setunion(setbinop((x,y)->(x+y), v), setbinop((x,y)->(x*y), v)); #v;} \\ Michel Marcus, Apr 13 2022

from math import prod
from itertools import combinations_with_replacement
def A263995(n): return len(set(sum(x) for x in combinations_with_replacement(range(1,n+1),2)) | set(prod(x) for x in combinations_with_replacement(range(1,n+1),2))) # Chai Wah Wu, Apr 15 2022

a(n) = A027424(n) + A108954(n). - Jon Maiga, Jan 03 2022

A062858 In the triangular multiplication table of size A062859(n), the smallest number which appears n times.

Original entry on oeis.org

1, 4, 12, 36, 60, 120, 120, 360, 360, 360, 840, 840, 2520, 2520, 2520, 2520, 2520, 5040, 5040, 5040, 5040, 5040, 5040, 10080, 10080, 27720, 27720, 27720, 27720, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440

Offset: 1

Ron Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

Smallest number to appear n times in any m X m multiplication table (excluding the numbers below the diagonals).

			a(4)=36 because 36 is the smallest number to appear 4 times in the triangular multiplication table of size A062859(4)=18.

Cf. A027424, A062851, A062854, A062855, A062856, A062857, A062859, A000217.

from itertools import count
from collections import Counter
def A062858(n):
    c = Counter()
    for m in count(1):
        for i in range(1,m+1):
            ij = i*m
            c[ij] += 1
            if c[ij]>=n:
                return ij # Chai Wah Wu, Oct 16 2023

More terms from Don Reble, Nov 08 2001

A110713 a(n) is the number of distinct products b_1b_2...*b_n where 1 <= b_i <= n.

Original entry on oeis.org

1, 3, 10, 25, 91, 196, 750, 1485, 3025, 5566, 23387, 38402, 163268, 284376, 500004, 795549, 3575781, 5657839, 25413850, 40027130, 66010230, 105164280, 490429875, 713491350, 1232253906

Offset: 1

Jonas Wallgren, Sep 15 2005

If * is changed to + the result is A002061. - Michel Marcus and David Galvin, Sep 19 2021

			a(2) = A027424(2) = 3.
a(3) = A027425(3) = 10.
a(4) = A100437(4) = 25.

Gerhard Kirchner, Theory and aspects of extension

Main diagonal of A322967.

Cf. A110713, A027424, A027425, A100437, A345882.

a(n) = my(l = List()); forvec(x = vector(n, i, [1,n]), listput(l, prod(i = 1, n, x[i])), 1); listsort(l, 1); #l \\ David A. Corneth, Jan 02 2019

from math import prod
from itertools import combinations_with_replacement
def A110713(n): return len({prod(d) for d in combinations_with_replacement(list(range(1,n+1)),n)}) # Chai Wah Wu, Sep 19 2021

a(10)-a(15) from Donovan Johnson, Dec 08 2009

a(16)-a(25) from Gerhard Kirchner, Dec 07 2015

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

cp's OEIS Frontend

A027428 Number of distinct products ij with 1 <= i < j <= n. (Number of terms appearing more than once in a 1-to-n multiplication table.)

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

A101301 The sum of the first n primes, minus n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A108407 Number of added unique known entries when going from the n X n to the (n+1) X (n+1) multiplication table.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

A225246 T(n,k)=Number of distinct values of the sum of n products of a 0..k-1 and a 0..k integer.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A263995 Cardinality of the union of the set of sums and the set of products made from pairs of integers from {1..n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Python

Formula

A062858 In the triangular multiplication table of size A062859(n), the smallest number which appears n times.

Views

Author

Keywords

Comments

A110713 a(n) is the number of distinct products b_1b_2...*b_n where 1 <= b_i <= n.