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
Keywords
Examples
Since 2 of 60's 12 divisors (30 and 60) are multiples of at least 3 consecutive primes, a(60) = 12 - 2 = 10.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..65537
- Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Programs
-
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
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(n) = Sum_{d|n} [A300820(d) < 3]. - Antti Karttunen, Mar 21 2018
Comments