A166469 Number of divisors of n which are not multiples of consecutive primes.

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

Offset

1,2

Comments

Links various subsequences of A025487 with an unusual number of important sequences, including the Fibonacci, Lucas, and other generalized Fibonacci sequences (see cross-references).

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, A167447.

Links

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

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 one or more nonadjacent exponents, plus 1. For example, if A001221(n) = 3, a(n) = e_1*e_3 + e_1 + e_2 + e_3 + 1. If A001221(n) = k, the total number of terms always equals A000045(k+2).

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 +1; for i > 2, r(i) = r(i-1) + e_i * r(i-2).

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 pair of consecutive primes as divisors.

a(n) = Sum_{d|n} (1-A296210(d)). - Antti Karttunen, Dec 15 2017

Example

Since 3 of 30's 8 divisors (6, 15, and 30) are multiples of 2 or more consecutive primes, a(30) = 8 - 3 = 5.

Mathematica

Array[DivisorSum[#, 1 &, FreeQ[Differences@ PrimePi@ FactorInteger[#][[All, 1]], 1] &] &, 105] (* Michael De Vlieger, Dec 16 2017 *)

Prog

(PARI)
A296210(n) = { if(1==n, return(0)); my(ps=factor(n)[, 1], pis=vector(length(ps), i, primepi(ps[i])), diffsminusones = vector(length(pis)-1, i, (pis[i+1]-pis[i])-1)); !factorback(diffsminusones); };
A166469(n) = sumdiv(n, d, !A296210(d)); \\ Antti Karttunen, Dec 15 2017

Crossrefs

Cf. A000040, A006094, A104210, A296210.

A(A002110(n)) = A000045(n+2); A(A097250(n)) = A000032(n+1). For more relationships involving Fibonacci and Lucas numbers, see A166470-A166473, comment on A081341.

A(A061742(n)) = A001045(n+2); A(A006939(n)) = A000085(n+1); A(A212170(n)) = A000142(n+1). A(A066120(n)) = A166474(n+1).

Sequence in context: A135981 A135615 A348856 * A080226 A060741 A125747

Adjacent sequences: A166466 A166467 A166468 * A166470 A166471 A166472

Keyword

nonn

Author

Matthew Vandermast, Nov 05 2009

Extensions

Edited by Matthew Vandermast, May 24 2012

Status

approved