A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n.
1, 2, 3, 4, 4, 6, 5, 7, 6, 7, 6, 11, 7, 9, 9, 10, 8, 12, 9, 13, 11, 11, 10, 17, 11, 12, 12, 14, 11, 18, 12, 16, 14, 14, 14, 20, 13, 15, 15, 20, 14, 20, 15, 19, 20, 17, 16, 25, 17, 20, 18, 20, 17, 23, 19, 24, 19, 19, 18, 29, 19, 21, 24, 24, 21, 25, 20, 24, 22, 27, 21, 32, 22, 24, 26
Offset: 1
Keywords
Examples
For n = 8 we have the following proper divisors for k <= n: {1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}. Only k = 6 has a proper divisor that is not a divisor of 8, viz. 3. Hence a(8) = 7.
Links
- Robert Israel, Table of n, a(n) for n = 1..10000
Programs
-
Magma
[ #[ k: k in [1..n] | forall(t){ d: d in Divisors(k) | d eq k or d in Divisors(n) } ]: n in [1..75] ]; -
Maple
N:= 1000: # to get a(1) to a(N) A:= Vector(N, numtheory:-tau): for p in select(isprime,[2,seq(i,i=3..N,2)]) do for d from 0 to floor(log[p](N))-1 do R:= [seq(seq(p^d*(i+p*j), j=1..floor((N/p^d - i)/p)), i=1..p-1)]; A[R]:= map(`+`,A[R],1); od od: convert(A,list); # Robert Israel, Nov 24 2015
-
Mathematica
f[n_] := Block[{d = Most@ Divisors@ n}, Select[Range@ n, Union[Most@ Divisors@ #, d] == d &]]; Array[Length@ f@ # &, {75}] (* Michael De Vlieger, Nov 25 2015 *) -
PARI
a004788(n) = {sfp = Set(); for (k=1, n-1, sfp = setunion(sfp, Set(factor(binomial(n, k))[, 1]))); return (length(sfp));} a(n) = numdiv(n) + a004788(n-1); \\ Altug Alkan, Nov 25 2015
Formula
a(n) = A000005(n) + A004788(n-1). - Vladeta Jovovic, Apr 07 2009 (Corrected by Altug Alkan, Nov 25 2015)
Extensions
Edited and extended by Klaus Brockhaus, Apr 06 2009
Comments