A038566 -id:A038566 - cp's OEIS frontend

A384046 Triangle in which the n-th row gives the numbers from 1 to n whose largest divisor that is a unitary divisor of n is 1.

1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 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 18 2025

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

Amiram Eldar, Table of n, a(n) for n = 1..10204 (first 170 rows flattened)
Eckford Cohen, Arithmetical functions associated with the unitary divisors of an integer, Mathematische Zeitschrift, Vol. 74 (1960), pp. 66-80.

The unitary analog of A038566.

Cf. A047994 (row lengths), A333576 (row sums), A077610, A225174, A384047.

udiv[n_] := Select[Divisors[n], CoprimeQ[#, n/#] &]; uGCD[n_, k_] := Max[Intersection[udiv[n], Divisors[k]]]; row[n_] := Select[Range[n], uGCD[n, #] == 1 &]; Array[row, 10] // Flatten

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

T(n, 1) = 1.

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Original entry on oeis.org

2, 3, 2, 4, 5, 2, 3, 4, 6, 7, 2, 4, 6, 8, 3, 6, 9, 2, 4, 5, 6, 8, 10, 11, 2, 3, 4, 6, 8, 9, 10, 12, 13, 2, 4, 6, 7, 8, 10, 12, 14, 3, 5, 6, 9, 10, 12, 15, 2, 4, 6, 8, 10, 12, 14, 16, 17, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 19, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 3, 6, 7, 9, 12, 14, 15

Offset: 2

Franklin T. Adams-Watters, Sep 11 2006

Row n contains numbers m <= n such that gcd(m,n) > 1, i.e., numbers m in the cototient of n. - Michael De Vlieger, Mar 13 2018

			2;
3;
2,4;
5;
2,3,4,6;
7;
...

Michael De Vlieger, Table of n, a(n) for n = 2..12949 (rows 2 <= n <= 256).

Cf. A051953 (row lengths), A038566, A081520, A133995 (nondivisors in the cototient of n).

Table[Select[Range@ n, ! CoprimeQ[#, n] &], {n, 20}] // Flatten (* Michael De Vlieger, Mar 13 2018 *)

A038610 Least common multiple of integers less than and prime to n.

Original entry on oeis.org

1, 1, 2, 3, 12, 5, 60, 105, 280, 63, 2520, 385, 27720, 6435, 8008, 45045, 720720, 85085, 12252240, 2909907, 3695120, 1322685, 232792560, 37182145, 1070845776, 128707425, 2974571600, 717084225, 80313433200, 215656441, 2329089562800

Offset: 1

Wouter Meeussen

If n is a prime power, tau(a(n)) is the number of times n occurs in A034699. (If n is not a prime power, it does not occur in A034699.) - Franklin T. Adams-Watters, Apr 01 2008

a(n) = lcm(A038566(n,k): k = 1..A000010(n)). - Reinhard Zumkeller, Sep 21 2013

			Since 1, 5, 7, and 11 are relatively prime to 12, a(12) = LCM(1,5,7,11) = 385.

T. D. Noe, Table of n, a(n) for n=1..200

Cf. A034699, A000005.

a038610 = foldl lcm 1 . a038566_row
-- Reinhard Zumkeller, Sep 21 2013, Oct 04 2011

A038610 := n -> ilcm(op(select(k->igcd(n,k)=1,[$1..n]))); # Peter Luschny, Jun 25 2011

Table[ LCM@@ Flatten[ Position[ GCD[ n, # ]& /@ Range[ n ], 1 ] ], {n, 32} ]
Join[{1},Table[LCM@@Select[Range[n-1],CoprimeQ[#,n]&],{n,2,40}]] (* Harvey P. Dale, Mar 05 2016 *)

a(n) = local(r); r=1;for(i=1,n-1,if(gcd(i,n)==1,r=lcm(r,i)));r \\ Franklin T. Adams-Watters, Apr 01 2008

a(n) = e^[Sum_{k=1..n} (1-floor(n^k/k)+floor((n^k -1)/k))*Mangoldt(k)] where Mangoldt is the Mangoldt function. - Anthony Browne, Jun 16 2016

A038569 Denominators in a certain bijection from positive integers to positive rationals.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

See A020652/A020653 for an alternative version where the fractions p/q are listed by increasing p+q, then p. - M. F. Hasler, Nov 25 2021

			First arrange the positive fractions p/q <= 1 by increasing denominator, then by increasing numerator:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, ... (this is A038566/A038567).
Now follow each but the first term by its reciprocal:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, ... (this is A038568/A038569).

H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Cf. A038566, A038567, A038568.

See A020652, A020653 for an alternative version.

with (numtheory): A038569 := proc (n) local sum, j, k; sum := 1: k := 2: while (sum < n) do: sum := sum + 2 * phi(k): k := k + 1: od: sum := sum - 2 * phi(k-1): j := 1: while sum < n do: if gcd(j,k-1) = 1 then sum := sum + 2: fi: j := j+1: od: if sum > n then RETURN (k-1) fi: RETURN (j-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := Module[{s = 1, k = 2, j = 1}, While[s <= n, s = s + 2*EulerPhi[k]; k = k+1]; s = s - 2*EulerPhi[k-1]; While[s <= n, If[GCD[j, k-1] == 1, s = s+2]; j = j+1]; If[s > n+1, k-1, j-1]]; Table[a[n], {n, 0, 99}](* Jean-François Alcover, Nov 10 2011, after Maple *)

a(n) = { my (e); for (q=1, oo, if (n+1<2*e=eulerphi(q), for (p=1, oo, if (gcd(p,q)==1, if (n+1<2, return ([q,p][n+2]), n-=2))), n-=2*e)) } \\ Rémy Sigrist, Feb 25 2021

from sympy import totient, gcd
def a(n):
    s=1
    k=2
    while s<=n:
        s+=2*totient(k)
        k+=1
    s-=2*totient(k - 1)
    j=1
    while s<=n:
        if gcd(j, k - 1)==1: s+=2
        j+=1
    if s>n + 1: return k - 1
    return j - 1 # Indranil Ghosh, May 23 2017, translated from Mathematica

More terms from Erich Friedman

Definition clarified by N. J. A. Sloane, Nov 25 2021

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60

Offset: 1

Labos Elemer

From Reinhard Zumkeller, Oct 27 2010: (Start)
Conjecture: the sequence is finite and 60 is the largest term, empirically verified up to 10^7;
A139555(a(n)) = A000010(a(n)). (End)
The sequence is indeed finite. Let pi*(x) denote the number of prime powers (including 1) up to x.  Dusart's bounds plus finite checking [up to 60184] shows that pi*(x) <= x/(log(x) - 1.1) + sqrt(x) for x >= 4.  phi(n) > n/(e^gamma log log n + 3/(log log n)) for n >= 3.  Convexity plus finite checking [up to 1096] allows a quick proof that phi(n) > pi*(n) for n > 420.  So if n > 420, the reduced residue system mod n must contain at least one number that is neither 1 nor a prime power. Hence 60 is the last term in the sequence. - Charles R Greathouse IV, Jul 14 2011

			RRS[ 60 ] = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}.

M. Dalezman, From 30 to 60 Is Not Twice as Hard, Mathematics Magazine, Vol. 73, No. 2 (Apr. 2000), pp. 151-153.
O. Ore and N. J. Fine, Reduced Residue Systems, American Mathematical Monthly Vol. 66, No. 10 (Dec., 1959), pp. 926-927.

Cf. A048597, A048862-A048869.

Cf. A010055, A038566.

a051250 n = a051250_list !! (n-1)
a051250_list = filter (all ((== 1) . a010055) . a038566_row) [1..]
-- Reinhard Zumkeller, May 27 2015, Dec 18 2011, Oct 27 2010

fQ[n_] := Union[# == 1 || Mod[#, # - EulerPhi[#]] == 0 & /@ Select[ Range@ n, GCD[#, n] == 1 &]] == {True}; Select[ Range@ 100, fQ] (* Robert G. Wilson v, Jul 11 2011 *)

isprimepower(n)=ispower(n,,&n);isprime(n)
is(n)=for(k=2,n-1,if(gcd(n,k)==1&&!isprimepower(k),return(0)));1 \\ Charles R Greathouse IV, Jul 14 2011

A057562 Number of partitions of n into parts all relatively prime to n.

Original entry on oeis.org

1, 1, 2, 2, 6, 2, 14, 6, 16, 7, 55, 6, 100, 17, 44, 32, 296, 14, 489, 35, 178, 77, 1254, 30, 1156, 147, 731, 142, 4564, 25, 6841, 390, 1668, 474, 4780, 114, 21636, 810, 4362, 432, 44582, 103, 63260, 1357, 4186, 2200, 124753, 364, 105604, 1232, 24482, 3583

Offset: 1

Leroy Quet, Oct 03 2000

nonn

p is prime iff a(p) = A000041(p)-1. - Lior Manor, Feb 04 2005

			The unrestricted partitions of 4 are 1+1+1+1, 1+1+2, 1+3, 2+2 and 4. Of these, only 1+1+1+1 and 1+3 contain parts which are all relatively prime to 4. So a(4) = 2.

Charles R Greathouse IV, Table of n, a(n) for n = 1..1000

Cf. A036998, A038566, A100347, A227296.

See also A098743 (parts don't divide n).

a057562 n = p (a038566_row n) n where
   p _          0 = 1
   p []         _ = 0
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013

Table[Count[IntegerPartitions@ n, k_ /; AllTrue[k, CoprimeQ[#, n] &]], {n, 52}] (* Michael De Vlieger, Aug 01 2017 *)

R(n, v)=if(#v<2 || n=0, sum(i=1, #v, R(n-v[i], v[1..i])))
a(n)=if(isprime(n), return(numbpart(n)-1)); R(n, select(k->gcd(k, n)==1, vector(n, i, i))) \\ Charles R Greathouse IV, Sep 13 2012

a(n)=polcoeff(1/prod(k=1,n,if(gcd(k,n)==1,1-x^k,1), O(x^(n+1))+1), n) \\ Charles R Greathouse IV, Sep 13 2012

Coefficient of x^n in expansion of 1/Product_{d : gcd(d, n)=1} (1-x^d). - Vladeta Jovovic, Dec 23 2004

More terms from Naohiro Nomoto, Feb 28 2002

Corrected by Vladeta Jovovic, Dec 23 2004

A073311 Number of squarefree numbers in the reduced residue system of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 4, 4, 3, 7, 4, 8, 5, 6, 7, 11, 6, 12, 7, 8, 9, 15, 8, 13, 10, 13, 9, 17, 8, 19, 13, 13, 13, 15, 11, 23, 15, 17, 14, 26, 11, 28, 17, 18, 18, 30, 15, 26, 17, 21, 19, 32, 16, 25, 20, 23, 23, 36, 15, 37, 25, 26, 26, 30, 18, 41, 26, 29, 22, 44, 22, 45, 30, 29, 29, 36

Offset: 1

Reinhard Zumkeller, Jul 25 2002

nonn

Number of positive squarefree numbers <= n that are relatively prime to n.

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; six of them are squarefree: 1, 2, 7, 11, 13 and 14, therefore a(15)=6. [Typo fixed by _Reinhard Zumkeller_, Mar 19 2010]

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Steven R. Finch, Unitarism and infinitarism.
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 49-50.

Cf. A073312, A005117, A000010, A048864, A048865, A065463.

a073311 = sum . map a008966 . a038566_row
-- Reinhard Zumkeller, Jul 04 2012

[&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // Marius A. Burtea, Jul 27 2019

with(numtheory): rad := n -> mul(p, p in factorset(n)):
seq(add(mobius(rad(n)*i)^2, i=1..n), n=1..100); # Ridouane Oudra, Jul 27 2019

a[n_] := Select[Range[n], SquareFreeQ[#] && CoprimeQ[#, n]&] // Length;
Array[a, 100] (* Jean-François Alcover, Dec 12 2021 *)

a(n)=my(s=1); forfactored(k=2,n-1, if(vecmax(k[2][,2])==1 && gcd(k[1],n)==1, s++)); s \\ Charles R Greathouse IV, Nov 05 2017

a(n) + A073312(n) = A000010(n).
Let s(n) = Sum_{k=1..n} a(k). Then s(n) is asymptotic to C*n^2 where C = (3/Pi^2)*alpha and alpha = Product_{p prime} (1 - 1/(p*(p+1))) = A065463 = 0.7044422009... [From discussions in Number Theory List, Apr 06 2004]
A175046(n) = a(n)*A008966(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = Sum_{k=1..A000010(n)} A008966(A038566(n,k)). - Reinhard Zumkeller, Jul 04 2012
a(n) = Sum_{i=1..n} mu(A007947(n)*i)^2, where mu is the Moebius function (A008683). - Ridouane Oudra, Jul 27 2019
a(n) = Sum_{1<=k<=n, gcd(n,k)=1} mu(k)^2. - Ridouane Oudra, May 25 2023

A038568 Numerators in canonical bijection from positive integers to positive rationals.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Even-indexed terms are positive integers in order, with m occurring phi(m) times. Preceding odd-indexed terms (except for missing initial 0) are the corresponding numbers <= m and relatively prime to m, in increasing order. The denominators are just this sequence shifted left. Thus each positive rational occurs exactly once as a ratio a(n)/a(n+1). - Franklin T. Adams-Watters, Dec 06 2006

			First arrange fractions by increasing denominator, then by increasing numerator:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, ... (this is A038566/A038567);
now follow each term (except the first) with its reciprocal:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, ... (this is A038568/A038569).

H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Cf. A020652, A020653, A038566, A038567, A038569.

using Nemo
function A038568List(len)
    a, A = QQ(0), []
    for n in 1:len
        a = next_minimal(a)
        push!(A, numerator(a))
    end
A end
A038568List(84) |> println # Peter Luschny, Mar 13 2018

with (numtheory): A038568 := proc (n) local sum, j, k; sum := 1: k := 2: while (sum < n) do: sum := sum + 2 * phi(k): k := k + 1: od: sum := sum - 2 * phi(k-1): j := 1: while sum < n do: if gcd(j,k-1) = 1 then sum := sum + 2: fi: j := j+1: od: if sum > n then RETURN (j-1) fi: RETURN (k-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := Module[{sum = 1, k = 2}, While[sum < n, sum = sum + 2*EulerPhi[k]; k = k+1]; sum = sum - 2*EulerPhi[k-1]; j = 1; While[sum < n, If[GCD[j, k-1] == 1, sum = sum+2]; j = j+1; ]; If[sum > n, Return[j-1]]; Return[k-1] ]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 21 2012, translated from Maple *)

a(n) = { my (e); for (q=1, oo, if (n+1<2*e=eulerphi(q), for (p=1, oo, if (gcd(p,q)==1, if (n+1<2, return ([p,q][n+2]), n-=2))), n-=2*e)) } \\ Rémy Sigrist, Feb 25 2021

from sympy import totient, gcd
def a(n):
    s=1
    k=2
    while sn: return j - 1
    return k - 1 # Indranil Ghosh, May 23 2017, translated from Mathematica

More terms from Erich Friedman

A036998 The number of decompositions of n into different parts relatively prime to n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 4, 2, 3, 2, 11, 2, 17, 3, 5, 5, 37, 3, 53, 5, 12, 7, 103, 5, 70, 10, 42, 11, 255, 4, 339, 23, 59, 22, 130, 11, 759, 32, 115, 22, 1259, 10, 1609, 44, 94, 64, 2589, 22, 1674, 40, 385, 84, 5119, 30, 1309, 79, 665, 162, 9791, 18, 12075, 217, 556, 276

Offset: 1

Wouter Meeussen

nonn

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

Cf. A057562, A038566, A079124.

a036998 n = p (a038566_row n) n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013

Table[ Coefficient[ Series[ Times@@((1+z^#)&/@Select[ Range[ q ], GCD[ #, q ]===1& ]), { z, 0, q} ], z^q ], {q, 128} ]

Offset corrected by Amiram Eldar, Apr 24 2020

A053570 Sum of totient functions over arguments running through reduced residue system of n.

Original entry on oeis.org

1, 1, 2, 3, 6, 5, 12, 13, 18, 15, 32, 21, 46, 35, 42, 49, 80, 49, 102, 71, 88, 85, 150, 89, 156, 125, 164, 137, 242, 113, 278, 213, 230, 217, 272, 191, 396, 275, 320, 261, 490, 237, 542, 369, 386, 401, 650, 355, 640, 431, 560, 507, 830, 449, 704, 551, 696, 643

Offset: 1

Labos Elemer, Jan 17 2000

nonn

Phi summation results over numbers not exceeding n are given in A002088 while summation over the divisor set of n would give n. This is a further way of Phi summation.

Equals row sums of triangle A143620. - Gary W. Adamson, Aug 27 2008

			Given n = 36, its reduced residue system is {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}; the Euler phi of these terms are {1, 4, 6, 10, 12, 16, 18, 22, 20, 28, 30, 24}. Summation over this last set gives 191. So a(36) = 191.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A000010, A002088.

Cf. A143620. - Gary W. Adamson, Aug 27 2008

A038566_row := proc(n)
    a := {} ;
    for m from 1 to n do
        if igcd(n,m) =1 then
            a := a union {m} ;
        end if;
    end do:
    a ;
end proc:
A053570 := proc(n)
    add(numtheory[phi](r),r=A038566_row(n)) ;
end proc:
seq(A053570(n),n=1..30) ; # R. J. Mathar, Jan 09 2017

Join[{1}, Table[Sum[EulerPhi[i] * KroneckerDelta[GCD[i, n], 1], {i, n - 1}], {n, 2, 60}]] (* Alonso del Arte, Nov 02 2014 *)

a(n) = Sum_{k>=1} A000010(A038566(n,k)). - R. J. Mathar, Jan 09 2017

cp's OEIS Frontend

A384046 Triangle in which the n-th row gives the numbers from 1 to n whose largest divisor that is a unitary divisor of n is 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A038610 Least common multiple of integers less than and prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A038569 Denominators in a certain bijection from positive integers to positive rationals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A057562 Number of partitions of n into parts all relatively prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A073311 Number of squarefree numbers in the reduced residue system of n.

Views