A056169 Number of unitary prime divisors of n.

0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 1, 0, 2, 0, 1, 1, 3, 1, 0, 2, 2, 2, 0, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 1, 0, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 0, 2, 3, 1, 1, 2, 3, 1, 0, 1, 2, 1, 1, 2, 3, 1, 1, 0, 2, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 0, 1, 3, 1, 1, 3

Offset: 1

Author

Labos Elemer, Jul 27 2000

Keywords

• nonn
• nice
• easy

Comments

The zeros of this sequences are the powerful numbers (A001694). There are no arbitrarily long subsequences with a given upper bound; for example, every sequence of 4 values includes one divisible by 2 but not 4, so there are no more than 3 consecutive zeros. Similarly, there can be no more than 23 consecutive values with none divisible by both 2 and 3 but neither 4 nor 9 (so a(n) >= 2), etc. In general, this gives an upper bound that is a (relatively) small multiple of the k-th primorial number (prime(k)#). One suspects that the actual upper bounds for such subsequences are quite a bit lower; e.g., Erdős conjectured that there are no three consecutive powerful numbers. - Franklin T. Adams-Watters, Aug 08 2006

In particular, for every A048670(k)*A002110(k) consecutive terms, at least one is greater than or equal to k. - Charlie Neder, Jan 03 2019

Following Catalan's conjecture (which became Mihăilescu's theorem in 2002), the first case of two consecutive zeros in this sequence is for a(8) and a(9), because 8 = 2^3 and 9 = 3^2, and there are no other consecutive zeros for consecutive powers. However, there are other pairs of consecutive zeros at powerful numbers (A001694, A060355). The next example is a(288) = a(289) = 0, because 288 = 2^5 * 3^2 and 289 = 17^2, then also a(675) and a(676). - Bernard Schott, Jan 06 2019

a(2k-1) is the number of primes p such that p || x + y and p^2 || x^(2k-1) + y^(2k-1) for some positive integers x and y. For any positive integers x, y and k > 1, there is no prime p such that p || x + y and p^2 || x^(2k) + y^(2k). - Jinyuan Wang, Apr 08 2020

Examples

			9 = 3^2 so a(9) = 0; 10 = 2 * 5 so a(10) = 2; 11 = 11^1 so a(11) = 1.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Catalan's Conjecture.
• Index entries for sequences computed from exponents in factorization of n.

Crossrefs

Cf. A001221, A001694, A002110, A034444, A056170, A055231, A076445, A162642, A275812, A295659, A295662, A295664, A001694.

See also A060355.

Cf. A077761, A085548.

Programs

Haskell

a056169 = length . filter (== 1) . a124010_row
-- Reinhard Zumkeller, Sep 10 2013

Maple

a:= n-> nops(select(i-> i[2]=1, ifactors(n)[2])):
seq(a(n), n=1..120);  # Alois P. Heinz, Mar 27 2017

Mathematica

Join[{0},Table[Count[Transpose[FactorInteger[n]][[2]],1],{n,2,110}]] (* Harvey P. Dale, Mar 15 2012 *)
Table[DivisorSum[n, 1 &, And[PrimeQ@ #, CoprimeQ[#, n/#]] &], {n, 105}] (* Michael De Vlieger, Nov 28 2017 *)

PARI

a(n)=my(f=factor(n)[,2]); sum(i=1,#f,f[i]==1) \\ Charles R Greathouse IV, Apr 29 2015

Python

from sympy import factorint
def a(n):
    f=factorint(n)
    return 0 if n==1 else sum(1 for i in f if f[i]==1)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 19 2017

Scheme

;; With memoization-macro definec.
(definec (A056169 n) (if (= 1 n) 0 (+ (if (= 1 (A067029 n)) 1 0) (A056169 (A028234 n))))) ;; Antti Karttunen, Nov 28 2017

Formula

A prime factor of n is unitary iff its exponent is 1 in prime factorization of n. In general, gcd(p, n/p) = 1 or = p.

Additive with a(p^e) = 1 if e = 1, 0 otherwise.

a(n) = #{k: A124010(n,k) = 1, k = 1..A001221}. - Reinhard Zumkeller, Sep 10 2013

From Antti Karttunen, Nov 28 2017: (Start)

a(1) = 0; for n > 1, a(n) = A063524(A067029(n)) + a(A028234(n)).

a(n) = A001221(A055231(n)) = A001222(A055231(n)).

a(n) = A001221(n) - A056170(n) = A001221(n) - A001221(A000188(n)).

a(n) = A001222(n) - A275812(n).

a(n) = A162642(n) - A295662(n).

a(n) <= A162642(n) <= a(n) + A295659(n).

a(n) <= A295664(n).

(End)

Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B - C), where B is Mertens's constant (A077761) and C = Sum_{p prime} (1/p^2) = 0.452247... (A085548). - Amiram Eldar, Sep 28 2023