|
%I #51 Mar 26 2023 02:17:18
%S 1,2,3,4,3,6,4,8,5,10,7,12,8,9,15,16,11,18,13,14,14,22,10,24,16,18,19,
%T 28,13,30,20,22,21,25,26,36,24,27,18,40,17,42,32,33,29,46,34,48,32,36,
%U 39,52,24,42,27,40,37,58,30,60,40,49,48,50,30,66,51,49,35,70,34,72,48
%N Number of numbers less than n that are infinitarily relatively prime to n; the infinitary Euler phi function.
%C Not the same as A091732.
%C Let E[n] be the set of different terms of A050376 for which n = Product_{q in E[n]}q. Put Z(n) = n^2/Product_{q in E[n]}(q+1). Then a(n) = Z(n) + o(n^eps), where eps>0 arbitrary small. In fact, in the limits of [2,1000] we have for 636 numbers |a(n)-Z(n)| <= 1/2, for 242 numbers 1/2 < |a(n)-Z(n)| <= 1, for 117 numbers 1 < |a(n)-Z(n)| < 2 and only for 4 numbers (namely, 308, 738, 846 and 966) 2 <= |a(n)-Z(n)| < 3. - _Vladimir Shevelev_, Apr 17 2010
%D V. S. Abramovich (Shevelev), On an analog of the Euler function, Proceeding of the North-Caucasus Center of the Academy of Sciences of the USSR (Rostov na Donu) (1981) No. 2, 13-17.
%D V. S. Shevelev, Multiplicative functions in the Fermi-Dirac arithmetic, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 28-43.
%H Amiram Eldar, <a href="/A064380/b064380.txt">Table of n, a(n) for n = 2..10000</a> (terms 2..2000 from Wouter Meeussen)
%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Unitarism and infinitarism</a>.
%H Steven R. Finch, <a href="/A007947/a007947.pdf">Unitarism and Infinitarism</a>, February 25, 2004. [Cached copy, with permission of the author]
%H Simon Litsyn and Vladimir S. Shevelev, <a href="http://www.emis.de/journals/INTEGERS/papers/h33/h33.Abstract.html">On factorization of integers with restrictions on the exponent</a>, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A33, 1-36.
%F a(n) = Sum_{t_1>=0} Sum_{t_2>=0}... Sum_{t_m>=0} (-1)^(t_1+...+t_m) *floor(n/(q_1^t_1*...*q_m^t_m)), where q_i are distinct terms of A050376, such that n=q_1*...*q_m. - _Vladimir Shevelev_, Apr 17 2010
%e irelprime[6] = {1, 4, 5} because iDivisors[6] = {1, 2, 3, 6} and iDivisors[4] = {1, 4} so 4 is infinitary_relatively_prime to 6 since it lacks common infinitary divisors with 6.
%e For n = 2 .. 8, irelprime[n] gives {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,4,5}, {1,2,3,4,5,6}, {1,3,5,7}.
%e Let n = 10000 = 16*625 (16 and 625 are terms of A050376). Then a(10000) = Sum_{t_1>=0} Sum_{t_2>=0}(-1)^(t_1+t_2) * floor(16*625/(16^t_1*625^t_2)) = 16*625 - 16 - 625 + 1 + floor(625/16) - floor(625/256) = 9397. Note that, Z(n) = 9396.7 - _Vladimir Shevelev_, Apr 17 2010
%p maxpowp := proc(p, n) local f; for f in ifactors(n)[2] do if op(1, f) = p then return op(2, f) ; end if; end do: return 0 ; end proc:
%p isidiv := proc(d, n) local n2, d2, p, j; if n mod d <> 0 then return false; end if; for p in numtheory[factorset](n) do n2 := maxpowp(p, n) ; n2 := convert(n2, base, 2) ; d2 := maxpowp(p, d) ; d2 := convert(d2, base, 2) ; for j from 1 to nops(d2) do if op(j, n2) = 0 and op(j, d2) <> 0 then return false; end if; end do: end do; return true; end proc:
%p idivisors := proc(n) local a, d; a := {} ; for d in numtheory[divisors](n) do if isidiv(d, n) then a := a union {d} ; end if; end do: a ; end proc:
%p isInfrelpr := proc(n, m) idivisors(n) intersect idivisors(m) = {1} ; end proc:
%p A064380 := proc(n) option remember; local a; a := 0 ; for m from 1 to n-1 do if isInfrelpr(m, n) then a := a+1 ; end if; end do ; a ; end proc: # _R. J. Mathar_, Feb 19 2011
%t Table[ Length[ irelprime[ n ] ], {n, 2, 128} ] (* with irelprime[ n ] defined in A064379 *)
%t infCoprimeQ[n1_, n2_] := Module[{g = GCD[n1, n2]}, If[g == 1, True, AllTrue[ FactorInteger[g][[;;, 1]], BitAnd @@ IntegerExponent[{n1, n2}, #] == 0 &]]]; a[n_] := Sum[Boole[infCoprimeQ[j, n]], {j, 1, n-1}]; Array[a, 100, 2] (* _Amiram Eldar_, Mar 26 2023 *)
%o (PARI) isinfcoprime(n1, n2) = {my(g = gcd(n1, n2), p, e1, e2); if(g == 1,return(1)); p = factor(g)[, 1]; for(i=1, #p, e1 = valuation(n1, p[i]); e2 = valuation(n2, p[i]); if(bitand(e1, e2) > 0, return(0))); 1; }
%o a(n) = sum(j = 1, n-1, isinfcoprime(j, n)); \\ _Amiram Eldar_, Mar 26 2023
%Y Cf. A000010, A037445, A050376, A064379, A091732.
%K nonn,nice
%O 2,2
%A _Wouter Meeussen_, Sep 27 2001
%E Name edited by _Peter Munn_, Nov 14 2022
|
