A167447 Number of divisors of n which are not multiples of 3 consecutive primes.

1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 7, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 10, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 10, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9, 2, 8

Offset

1,2

Comments

If a number is a product of any number of consecutive primes, the number of its divisors which are not multiples of n consecutive primes is always a Fibonacci n-step number. See also A073485, A166469.

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number

Formula

a) If n has no prime gaps in its factorization (cf. A073491), then, if the canonical factorization of n into prime powers is the product of p_i^(e_i), a(n) is the sum of all products of exponents which do not include 3 consecutive exponents, plus 1. For example, if A001221(n)=3, a(n)=e_1*e_2 +e_1*e_3 +e_2*e_3 +e_1 +e_2 +e_3 +1. If A001221(n)=k, the total number of terms always equals A000073(k+3).

The answer can also be computed in k steps, by finding the answers for the products of the first i powers for i=1 to i=k. Let the result of the i-th step be called r(i). r(1)=e_1+1; r(2)=e_1*e_2+e_1+e_2+1; r(3)=e_1*e_2+e_1*e_3+e_2*e_3+e_1+e_2+e_3+1; for i>3, r(i)=r(i-1)+e_i*r(i-2)+e_i*e-(i-1)*r(i-3).

b) If n has prime gaps in its factorization, express it as a product of the minimum number of A073491's members possible. Then apply either of the above methods to each of those members, and multiply the results to get a(n). a(n)=A000005(n) iff n has no triple of consecutive primes as divisors.

a(A002110(n)) = A000073(n+2).

a(n) = Sum_{d|n} [A300820(d) < 3]. - Antti Karttunen, Mar 21 2018

Example

Since 2 of 60's 12 divisors (30 and 60) are multiples of at least 3 consecutive primes, a(60) = 12 - 2 = 10.

Prog

(PARI)
A300820(n) = if(omega(n)<=1, omega(n), my(pis=apply(p->primepi(p), factor(n)[, 1]), el=1, m=1); for(i=2, #pis, if(pis[i] == (1+pis[i-1]), el++; m = max(m, el), el=1)); (m));
A167447(n) = sumdiv(n, d, (A300820(d)<3)); \\ Antti Karttunen, Mar 21 2018

Crossrefs

Cf. A000040, A000073, A002110, A046301, A073485, A166469, A300820.

Sequence in context: A365208 A322986 A335519 * A134687 A184395 A329484

Adjacent sequences: A167444 A167445 A167446 * A167448 A167449 A167450

Keyword

nonn

Author

Matthew Vandermast, Nov 05 2009

Status

approved