A339509 Number of subsets of {1..n} whose elements have the same greatest prime factor.

1, 2, 3, 4, 6, 7, 9, 10, 14, 18, 20, 21, 29, 30, 32, 36, 44, 45, 61, 62, 70, 74, 76, 77, 109, 125, 127, 191, 199, 200, 232, 233, 249, 253, 255, 271, 399, 400, 402, 406, 470, 471, 503, 504, 512, 640, 642, 643, 899, 963, 1219, 1223, 1231, 1232, 1744, 1760, 1888

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Greatest Prime Factor

Example

a(8) = 14 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {2, 4}, {2, 8}, {3, 6}, {4, 8} and {2, 4, 8}.

Maple

b:= proc(n) option remember; `if`(n<2, 0,
      b(n-1)+x^max(numtheory[factorset](n)))
    end:
a:= n-> `if`(n<2, n+1, (p-> 2+add(2^
    coeff(p, x, i)-1, i=2..degree(p)))(b(n))):
seq(a(n), n=0..70);  # Alois P. Heinz, Dec 07 2020

Mathematica

b[n_] := b[n] = If[n < 2, 0,
     b[n - 1] + x^Max[FactorInteger[n][[All, 1]]]];
a[n_] := If[n < 2, n + 1, Function[p, 2 + Sum[2^
     Coefficient[p, x, i] - 1, {i, 2, Exponent[p, x]}]][b[n]]];
Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Jul 09 2021, after Alois P. Heinz *)

Prog

(Python)
from sympy import primefactors
def test(n):
    if n<2: return n
    return max(primefactors(n))
def a(n):
    tests = [test(i) for i in range(n+1)]
    return sum(2**tests.count(v)-1 for v in set(tests))
print([a(n) for n in range(57)]) # Michael S. Branicky, Dec 11 2020

Crossrefs

Cf. A006530, A339510.

Sequence in context: A071689 A187092 A076679 * A060233 A235203 A187102

Adjacent sequences: A339506 A339507 A339508 * A339510 A339511 A339512

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 07 2020

Extensions

a(24)-a(56) from Alois P. Heinz, Dec 07 2020

Status

approved