A064380 Number of numbers less than n that are infinitarily relatively prime to n; the infinitary Euler phi function.
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, 28, 13, 30, 20, 22, 21, 25, 26, 36, 24, 27, 18, 40, 17, 42, 32, 33, 29, 46, 34, 48, 32, 36, 39, 52, 24, 42, 27, 40, 37, 58, 30, 60, 40, 49, 48, 50, 30, 66, 51, 49, 35, 70, 34, 72, 48
Offset: 2
Examples
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.
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}.
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
References
- 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.
- V. S. Shevelev, Multiplicative functions in the Fermi-Dirac arithmetic, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 28-43.
Links
- Amiram Eldar, Table of n, a(n) for n = 2..10000 (terms 2..2000 from Wouter Meeussen)
- Steven R. Finch, Unitarism and infinitarism.
- Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
- Simon Litsyn and Vladimir S. Shevelev, On factorization of integers with restrictions on the exponent, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A33, 1-36.
Programs
-
Maple
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: 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: 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: isInfrelpr := proc(n, m) idivisors(n) intersect idivisors(m) = {1} ; end proc: 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 -
Mathematica
Table[ Length[ irelprime[ n ] ], {n, 2, 128} ] (* with irelprime[ n ] defined in A064379 *) 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 *) -
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; } a(n) = sum(j = 1, n-1, isinfcoprime(j, n)); \\ Amiram Eldar, Mar 26 2023
Formula
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
Extensions
Name edited by Peter Munn, Nov 14 2022
Comments