A385195 The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is either 1 or 2.

1, 2, 2, 3, 4, 4, 6, 7, 8, 8, 10, 6, 12, 12, 8, 15, 16, 16, 18, 12, 12, 20, 22, 14, 24, 24, 26, 18, 28, 16, 30, 31, 20, 32, 24, 24, 36, 36, 24, 28, 40, 24, 42, 30, 32, 44, 46, 30, 48, 48, 32, 36, 52, 52, 40, 42, 36, 56, 58, 24, 60, 60, 48, 63, 48, 40, 66, 48, 44

Offset

1,2

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Formula

Multiplicative with a(p^e) = 2 if p = 2 and e = 1, and p^e - 1 otherwise.

In general, the number of integers k from 1 to n such that ugcd(n, k), the greatest divisor of k that is a unitary divisor of n, is either 1 or a prime power q is a multiplicative function f(n) with f(p^e) = q if p^e = q, and p^e - 1 otherwise.

a(n) = A138191(n) * A047994(n), i.e., a(n) = 2*A047994(n) if n == 2 (mod 4) and A047994(n) otherwise.

In general, the number of integers k from 1 to n such that ugcd(n, k) is either 1 or a prime power q is (q/(q-1))*A047994(n) if q is a unitary divisor of n, and A047994(n) otherwise.

Sum_{k=1..n} a(k) ~ (23/40) * c * n^2, where c = Product_{p prime} (1 - 1/(p*(p+1))) = A065463.

In general, the average order of the number of integers k from 1 to n such that ugcd(n, k) is either 1 or a prime p is ((p^4+p^3-1)/(p^4+p^3-p^2)) * c * n^2 / 2, where c = A065463.

Example

For n = 6, the greatest divisor of k that is a unitary divisor of 6 for k = 1 to 6 is 1, 2, 3, 2, 1 and 6, respectively. 4 of the values are either 1 or 2, and therefore a(6) = 4.

Mathematica

f[p_, e_] := p^e - 1; f[2, 1] = 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

Prog

(PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, f[i, 1]^f[i, 2] - if(f[i, 1] == 2 && f[i, 2] == 1, 0, 1)); }

Crossrefs

The unitary analog of A126246 (with respect to the definition "the number of integers k from 1 to n such that gcd(n,k) is either 1 or 2").

Cf. A065463, A077610, A138191, A384047.

The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is: A047994 (1), A384048 (squarefree), A384049 (cubefree), A384050 (powerful), A384051 (cubefull), A384052 (square), A384053 (cube), A384054 (exponentially odd), A384055 (odd), A384056 (power of 2), A384057 (3-smooth), A384058 (5-rough), this sequence (1 or 2), A385196 (prime), A385197 (noncomposite), A385198 (prime power), A385199 (1 or prime power).

Sequence in context: A345141 A239950 A077768 * A143038 A029040 A053281

Adjacent sequences: A385192 A385193 A385194 * A385196 A385197 A385198

Keyword

nonn,easy,mult

Author

Amiram Eldar, Jun 21 2025

Status

approved