login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A010846 Number of numbers <= n whose set of prime factors is a subset of the set of prime factors of n. 51

%I #68 Oct 30 2023 07:18:29

%S 1,2,2,3,2,5,2,4,3,6,2,8,2,6,5,5,2,10,2,8,5,7,2,11,3,7,4,8,2,18,2,6,6,

%T 8,5,14,2,8,6,11,2,19,2,9,8,8,2,15,3,12,6,9,2,16,5,11,6,8,2,26,2,8,8,

%U 7,5,22,2,10,6,20,2,18,2,9,9,10,5,23,2,14,5,9,2,28,5,9,7,11,2,32,5,10

%N Number of numbers <= n whose set of prime factors is a subset of the set of prime factors of n.

%C This function of n appears in an ABC-conjecture by Andrew Granville. See Goldfeld. - _T. D. Noe_, Jun 30 2009

%H Michael De Vlieger, <a href="/A010846/b010846.txt">Table of n, a(n) for n = 1..10000</a> (first 5000 terms from T. D. Noe)

%H Dorian Goldfled, <a href="http://www.math.columbia.edu/~goldfeld/ABC-Conjecture.pdf">Modular forms, elliptic curves, and the ABC conjecture</a>

%F a(n) = |{k<=n, k|n^(tau(k)-1)}|. - _Vladeta Jovovic_, Sep 13 2006

%F a(n) = Sum_{j = 1..n} Product_{primes p | j} delta(n mod p,0) where delta is the Kronecker delta. - _Robert Israel_, Feb 09 2015

%F a(n) = Sum_{1<=k<=n,(n,k)=1} mu(k)*floor(n/k). - _Benoit Cloitre_, May 07 2016

%F a(n) = Sum_{k=1..n} floor(n^k/k)-floor((n^k -1)/k). - _Anthony Browne_, May 28 2016

%e From _Wolfdieter Lang_, Jun 30 2014: (Start)

%e a(1) = 1 because the empty set is a subset of any set.

%e a(6) = 5 from the five numbers: 1 with the empty set, 2 with the set {2}, 3 with {3}, 4 with {2} and 6 with {2,3}, which are all subsets of {2,3}. 5 is out because {5} is not a subset of {2,3}. (End)

%e From _David A. Corneth_, Feb 10 2015: (Start)

%e Let p# be the product of primes up to p, A002110. Then,

%e a(13#) = 1161

%e a(17#) = 4843

%e a(19#) = 19985

%e a(23#) = 83074

%e a(29#) = 349670

%e a(31#) = 1456458

%e a(37#) = 6107257

%e a(41#) = 25547835

%e (End)

%p A:= proc(n) local F, S, s,j,p;

%p F:= numtheory:-factorset(n);

%p S:= {1};

%p for p in F do

%p S:= {seq(seq(s*p^j, j=0..floor(log[p](n/s))),s=S)}

%p od;

%p nops(S)

%p end proc;

%p seq(A(n),n=1..1000); # _Robert Israel_, Jun 27 2014

%t pf[n_] := If[n==1, {}, Transpose[FactorInteger[n]][[1]]]; SubsetQ[lst1_, lst2_] := Intersection[lst1,lst2]==lst1; Table[pfn=pf[n]; Length[Select[Range[n], SubsetQ[pf[ # ],pfn] &]], {n,100}] (* _T. D. Noe_, Jun 30 2009 *)

%t Table[Total[MoebiusMu[#] Floor[n/#] &@ Select[Range@ n, CoprimeQ[#, n] &]], {n, 92}] (* _Michael De Vlieger_, May 08 2016 *)

%o (PARI) a(n,f=factor(n)[,1])=if(#f>1,my(v=f[1..#f-1],p=f[#f],s); while(n>0, s+=a(n,v); n\=p); s, if(#f&&n>0,log(n+.5)\log(f[1])+1,n>0)) \\ _Charles R Greathouse IV_, Jun 27 2013

%o (PARI) a(n) = sum(k=1,n,if(gcd(n,k)-1,0,moebius(k)*(n\k))) \\ _Benoit Cloitre_, May 07 2016

%o (PARI) a(n,f=factor(n)[,1])=if(#f<2, return(if(#f, valuation(n,f[1])+1, 0))); my(v=f[1..#f-1],p=f[#f],s); while(n, s+=a(n,v); n\=p); s \\ _Charles R Greathouse IV_, Nov 03 2021

%Y Cf. A162306 (numbers for each n).

%K nonn,easy

%O 1,2

%A _Olivier GĂ©rard_

%E Definition made more precise at the suggestion of _Wolfdieter Lang_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:57 EDT 2024. Contains 371265 sequences. (Running on oeis4.)