A339510 Number of subsets of {1..n} whose elements have the same smallest prime factor.

1, 2, 3, 4, 6, 7, 11, 12, 20, 22, 38, 39, 71, 72, 136, 140, 268, 269, 525, 526, 1038, 1046, 2070, 2071, 4119, 4121, 8217, 8233, 16425, 16426, 32810, 32811, 65579, 65611, 131147, 131151, 262223, 262224, 524368, 524432, 1048720, 1048721, 2097297, 2097298

Offset

0,2

Links

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

Eric Weisstein's World of Mathematics, Least Prime Factor

Formula

a(n) ~ 2^(n/2) if n is even and a(n) ~ 2^((n-1)/2) if n is odd. - Vaclav Kotesovec, Jul 10 2021

Example

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

Maple

b:= proc(n) option remember; `if`(n<2, 0,
      b(n-1)+x^min(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..60);  # Alois P. Heinz, Dec 07 2020

Mathematica

b[n_] := b[n] = If[n<2, 0, b[n-1] + x^Min[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, 60}] (* Jean-François Alcover, Jul 10 2021, after Alois P. Heinz *)

Prog

(Python)
from sympy import primefactors
def test(n):
    if n<2: return n
    return min(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(44)]) # Michael S. Branicky, Dec 07 2020

Crossrefs

Cf. A020639, A339509.

Sequence in context: A325769 A360955 A226538 * A191930 A202113 A113243

Adjacent sequences: A339507 A339508 A339509 * A339511 A339512 A339513

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 07 2020

Extensions

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

Status

approved