login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339510 Number of subsets of {1..n} whose elements have the same smallest prime factor. 2
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 (list; graph; refs; listen; history; text; internal format)
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: A237667 A325769 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 08:06 EDT 2021. Contains 348150 sequences. (Running on oeis4.)