cp's OEIS Frontend

A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

%I A384041 #7 May 18 2025 04:29:34
%S A384041 1,2,3,3,5,6,7,7,8,10,11,9,13,14,15,13,17,16,19,15,21,22,23,21,24,26,
%T A384041 25,21,29,30,31,27,33,34,35,24,37,38,39,35,41,42,43,33,40,46,47,39,48,
%U A384041 48,51,39,53,50,55,49,57,58,59,45,61,62,56,53,65,66,67,51
%N A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.
%H A384041 Amiram Eldar, <a href="/A384041/b384041.txt">Table of n, a(n) for n = 1..10000</a>
%F A384041 Multiplicative with a(p^e) = ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1).
%F A384041 a(n) >= A000010(n), with equality if and only if n = 1.
%F A384041 Dirichlet g.f.: (zeta(s-1)*zeta(2*s)/zeta(s)) * Product_{p prime} (1 + 1/p^s - 1/p^(3*s)).
%F A384041 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/(p^2+1)) = 0.93749428273130025078... .
%t A384041 f[p_, e_] := ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]
%o A384041 (PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, ((f[i,1]^2+f[i,1]-1)*f[i,1]^(f[i,2]-1) - (-1)^f[i,2])/(f[i,1] + 1));}
%Y A384041 Cf. A000010, A268335.
%Y A384041 The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), A384040 (cubefull), this sequence (exponentially odd), A384042 (5-rough).
%K A384041 nonn,easy,mult
%O A384041 1,2
%A A384041 _Amiram Eldar_, May 18 2025