A064379 -id:A064379 - cp's OEIS frontend

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

Wouter Meeussen, Sep 27 2001

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

			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

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.

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.

Cf. A000010, A037445, A050376, A064379, A091732.

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

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 *)

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

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

Name edited by Peter Munn, Nov 14 2022

A372328 a(n) is the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 1, 5, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 8, 7, 5, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 5, 2, 1, 1, 1, 8, 27, 1, 1, 2, 1, 1, 1

Offset: 1

Amiram Eldar, Apr 28 2024

First differs from A331738 at n = 32.

The largest divisor d of n that is infinitarily relatively prime to n (see A064379), i.e., d have no common infinitary divisors with n.

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

Cf. A036537, A064379, A077609, A331738, A372329.

Similar sequences: A365297, A365298, A365637, A365685, A367931, A367932.

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

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

Multiplicative with a(p^e) = p^(2^ceiling(log_2(e+1)) - e - 1).
a(n) = A372329(n)/n.
a(n) = 1 if and only if n is in A036537.
a(n) <= n, with equality if and only if n = 1.

A384246 Triangle in which the n-th row gives the numbers from 1 to n whose largest divisor that is an infinitary divisor of n is 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 3, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 5, 7, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 5, 9, 11, 13, 1, 2, 4, 7, 8, 11, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Offset: 1

Amiram Eldar, May 23 2025

			Triangle begins:
  1
  1
  1, 2
  1, 2, 3
  1, 2, 3, 4
  1, 5
  1, 2, 3, 4, 5, 6
  1, 3, 5, 7
  1, 2, 3, 4, 5, 6, 7, 8
  1, 3, 7, 9
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  1, 2, 5, 7, 10, 11
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
  1, 3, 5, 9, 11, 13
  1, 2, 4, 7, 8, 11, 13, 14

Amiram Eldar, Table of n, a(n) for n = 1..10276 (first 175 rows flattened)

Cf. A064379, A384046, A384245, A384247 (row lengths), A384248 (row sums).

infdivs[n_] := If[n == 1, {1}, Sort@ Flatten@ Outer[Times, Sequence @@ (FactorInteger[n] /. {p_, m_Integer} :> p^Select[Range[0, m], BitOr[m, #] == m &])]]; (* Michael De Vlieger at A077609 *)
infGCD[n_, k_] := Max[Intersection[infdivs[n], Divisors[k]]];
row[n_] := Select[Range[n], infGCD[n, #] == 1 &]; Array[row, 16] // Flatten

isidiv(d, f) = {if (d==1, return (1)); for (k=1, #f~, bne = binary(f[k, 2]); bde = binary(valuation(d, f[k, 1])); if (#bde < #bne, bde = concat(vector(#bne-#bde), bde)); for (j=1, #bne, if (! bne[j] && bde[j], return (0)); ); ); return (1); }
infdivs(n) = {my(f = factor(n), d = divisors(f), idiv = []); for (k=1, #d, if (isidiv(d[k], f), idiv = concat(idiv, d[k])); ); idiv; } \\ Michel Marcus at A077609
infgcd(n, k) = vecmax(setintersect(infdivs(n), divisors(k)));
row(n) = select(x -> infgcd(n, x) == 1, vector(n, i, i));

A372331 The number of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 4, 4, 1, 1, 2, 1, 1, 1

Offset: 1

Amiram Eldar, Apr 28 2024

First differs from A370077 and A370080 at n = 32.
The number of divisors d of n that are infinitarily relatively prime to n (see A064379), i.e., d have no common infinitary divisors with n.
Equivalently, the number of divisors d of n such that for each prime divisor p of d, bitand(v_p(n), v_p(d)) = 0, where v_p(k) is the highest power of p that divides k. Note that for infinitary divisors d of n (A077609), bitand(v_p(n), v_p(d)) = v_p(d).

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

Cf. A036537, A037445, A064379, A077609, A080100, A372328.

Cf. A370077, A370080.

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

a(n) = vecprod(apply(x -> 2^(logint(x, 2) + 1 - hammingweight(x)), factor(n)[, 2]));

a(n) = A037445(A372328(n)).
Multiplicative with a(p^e) = 2^A023416(e) = A080100(e).
a(n) = 1 if and only if n is in A036537.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} (1 + Sum_{k>=1} A080100(k)/p^k) = 1.51209151045338102469... .

A372692 The sum of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 1, 1, 4, 1, 1, 3, 1, 1, 1, 15, 1, 4, 1, 3, 1, 1, 1, 1, 6, 1, 1, 3, 1, 1, 1, 5, 1, 1, 1, 12, 1, 1, 1, 1, 1, 1, 1, 3, 4, 1, 1, 15, 8, 6, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 4, 3, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 6, 3, 1, 1, 1, 15, 40, 1, 1, 3, 1, 1

Offset: 1

Amiram Eldar, May 10 2024

The sum of divisors d of n that are infinitarily relatively prime to n (see A064379), i.e., d have no common infinitary divisors with n.

The numbers of these divisors is A372331(n) and the largest of them is A372328(n).

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

Cf. A001146, A036537, A049417, A064379, A372328, A372331.

f[p_, e_] := p^(2^(-1 + Position[Reverse@ IntegerDigits[e, 2], ?(# == 0 &)])); a[1] = 1; a[n] := Times @@ (Flatten@ (f @@@ FactorInteger[n]) + 1); Array[a, 100]

s(n) = apply(x -> 1 - x, binary(n));
a(n) = {my(f = factor(n), k); prod(i = 1, #f~, k = s(f[i, 2]); prod(j = 1, #k, if(k[j], f[i, 1]^(2^(#k-j)) + 1, 1)));}

Multiplicative with a(p^e) = Product_{k >= 0, 2^k < e, bitand(e, 2^k) = 0} (p^(2^k) + 1).
a(n) >= 1, with equality if and only if n is in A036537.
a(n) <= n-1, with equality if and only if n = 2^(2^k) for k >= 0.

A301866 Numbers k such that iphi(k) = iphi(k+1), where iphi is the infinitary totient function (A064380).

Original entry on oeis.org

1, 21, 143, 208, 314, 459, 957, 1652, 2685, 5091, 20155, 38180, 41265, 45716, 54722, 116937, 161001, 186794, 230390, 274533, 338547, 416577, 430137, 495187

Offset: 1

Amiram Eldar, Mar 28 2018

a(16) > 10^5. - Robert Price, May 22 2018

			iphi(21) = iphi(22) = 14, thus 21 is in the sequence.

Cf. A064379, A064380.

irelprime[n_] := Select[temp = iDivisors[n]; Range[n], Intersection[iDivisors[#], temp] === {1} &]; bitty[k_] := Union[Flatten[Outer[Plus, Sequence @@ {0, #1} & /@ Union[2^Range[0, Floor[Log[2, k]]]*Reverse[IntegerDigits[k, 2]]]]]];
  iDivisors[k_Integer] := Sort[(Times @@ (First[it]^(#1 /. z -> List)) &) /@ Flatten[Outer[z, Sequence @@ bitty /@ Last[it = Transpose[FactorInteger[k]]], 1]]]; iDivisors[1] := {1}; iphi[n_] := Length[irelprime[n]]; iphiQ[n_] := iphi[n] == iphi[n + 1]; Select[Range[10^3], iphiQ](* after Wouter Meeussen at A064379 *)

a(11)-a(15) from Robert Price, May 22 2018

a(16)-a(24) from Amiram Eldar, Mar 26 2023

A384245 Triangle read by rows: T(n, k) for 1 <= k <= n is the largest divisor of k that is an infinitary divisor of n.

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 1, 5, 1, 2, 3, 2, 1, 6, 1, 1, 1, 1, 1, 1, 7, 1, 2, 1, 4, 1, 2, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 3, 4, 1, 3, 1, 4, 3, 1, 1, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13

Offset: 1

Amiram Eldar, May 23 2025

First differs from A384047 at n = 30.

			Triangle begins:
  1
  1, 2
  1, 1, 3
  1, 1, 1, 4
  1, 1, 1, 1, 5
  1, 2, 3, 2, 1, 6
  1, 1, 1, 1, 1, 1, 7
  1, 2, 1, 4, 1, 2, 1, 8
  1, 1, 1, 1, 1, 1, 1, 1, 9
  1, 2, 1, 2, 5, 2, 1, 2, 1, 10

Amiram Eldar, Table of n, a(n) for n = 1..10153 (first 142 rows flattened)

Cf. A050873, A064379, A077609, A384047, A384246 (positions of 1's).

infdivs[n_] := If[n == 1, {1}, Sort@ Flatten@ Outer[Times, Sequence @@ (FactorInteger[n] /. {p_, m_Integer} :> p^Select[Range[0, m], BitOr[m, #] == m &])]];  (* Michael De Vlieger at A077609 *)
T[n_, k_] := Max[Intersection[infdivs[n], Divisors[k]]];
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten

isidiv(d, f) = {if (d==1, return (1)); for (k=1, #f~, bne = binary(f[k, 2]); bde = binary(valuation(d, f[k, 1])); if (#bde < #bne, bde = concat(vector(#bne-#bde), bde)); for (j=1, #bne, if (! bne[j] && bde[j], return (0)); ); ); return (1); }
infdivs(n) = {my(f = factor(n), d = divisors(f), idiv = []); for (k=1, #d, if (isidiv(d[k], f), idiv = concat(idiv, d[k])); ); idiv; } \\ Michel Marcus at A077609
T(n, k) = vecmax(setintersect(infdivs(n), divisors(k)));

A384244 Triangle in which the n-th row gives the numbers k from 1 to n such that the greatest common unitary divisor of k and n is 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 3, 4, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 5, 7, 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 4, 5, 8, 9, 11, 12, 13, 1, 2, 4, 7, 8, 9, 11, 13, 14

Offset: 1

Amiram Eldar, May 23 2025

			Triangle begins:
  1
  1
  1, 2
  1, 2, 3
  1, 2, 3, 4
  1, 4, 5
  1, 2, 3, 4, 5, 6
  1, 2, 3, 4, 5, 6, 7
  1, 2, 3, 4, 5, 6, 7, 8
  1, 3, 4, 7, 8, 9

Amiram Eldar, Table of n, a(n) for n = 1..10349 (first 160 rows flattened)
László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, Journal of Integer Sequences, Vol. 12 (2009), Article 09.5.2.

The bi-unitary analog of A038566.

Cf. A116550 (row lengths), A200723 (row sums), A077610, A089912, A165430, A225174, A064379 (infinitary analog), A384046 (unitary analog).

udiv[n_] := Select[Divisors[n], CoprimeQ[#, n/#] &];
ugcd[n_, m_] := Max[Intersection[udiv[n], udiv[m]]];
row[n_] := Select[Range[n], ugcd[n, #] == 1 &]; Array[row, 15] // Flatten

udiv(n) = select(x -> gcd(x, n/x) == 1, divisors(n));
ugcd(n, m) = vecmax(setintersect(udiv(n), udiv(m)));
row(n) = select(x -> ugcd(n, x) == 1, vector(n, i, i));

cp's OEIS Frontend

A064380 Number of numbers less than n that are infinitarily relatively prime to n; the infinitary Euler phi function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A372328 a(n) is the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384246 Triangle in which the n-th row gives the numbers from 1 to n whose largest divisor that is an infinitary divisor of n is 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A372331 The number of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A372692 The sum of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301866 Numbers k such that iphi(k) = iphi(k+1), where iphi is the infinitary totient function (A064380).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A384245 Triangle read by rows: T(n, k) for 1 <= k <= n is the largest divisor of k that is an infinitary divisor of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI