login
A064380
Number of numbers less than n that are infinitarily relatively prime to n; the infinitary Euler phi function.
27
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,2
COMMENTS
Not the same as A091732.
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
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.
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
EXAMPLE
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Wouter Meeussen, Sep 27 2001
EXTENSIONS
Name edited by Peter Munn, Nov 14 2022
STATUS
approved