login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

For primes p, a(p) = A036234(p) = A000720(p) + 1.

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

FORMULA

a(n) = A000005(n) + A004788(n-1). - Vladeta Jovovic, Apr 07 2009 (Corrected by Altug Alkan, Nov 25 2015)

EXAMPLE

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.

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 *)

PROG

(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] ];

(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

CROSSREFS

Cf. A000040, A000720, A036234.

Sequence in context: A181833 A202650 A228286 * A071323 A071324 A063655

Adjacent sequences:  A158970 A158971 A158972 * A158974 A158975 A158976

KEYWORD

nonn

AUTHOR

Jaroslav Krizek, Apr 01 2009

EXTENSIONS

Edited and extended by Klaus Brockhaus, Apr 06 2009

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 07:01 EST 2018. Contains 299358 sequences. (Running on oeis4.)