A009195 -id:A009195 - cp's OEIS frontend

A327161 Number of positive integers that are reachable from n with some combination of transitions x -> usigma(x)-x and x -> gcd(x,phi(x)), where usigma is the sum of unitary divisors of n (A034448), and phi is Euler totient function (A000010).

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

Offset: 1

Antti Karttunen, Aug 25 2019

nonn

Question: Is this sequence well-defined for every n > 0? If A318882 is not well-defined for all positive integers, then neither can this be.

			a(30) = 10 as the graph obtained from vertex-relations x -> A034460(x) and x -> A009195(x) spans the following ten numbers [1, 2, 4, 6, 8, 12, 18, 30, 42, 54], which is illustrated below:
.
  30 -> 42 -> 54 (-> 30 ...)
   |     |     |
   2 <-- 6 <- 18
   |  \        |
   1 <-- 4 <- 12
            \  |
             <-8

Antti Karttunen, Table of n, a(n) for n = 1..20000
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A000010, A009195, A034448, A034460, A318882, A326195.

Cf. also A326196, A326198, A327160.

A034460(n) = (sumdivmult(n, d, if(gcd(d, n/d)==1, d))-n); \\ From A034460
A327161aux(n,xs) = if(vecsearch(xs,n),xs, xs = setunion([n],xs); if(1==n,xs, my(a=A034460(n), b=gcd(eulerphi(n),n)); xs = A327161aux(a,xs); if((a==b),xs, A327161aux(b,xs))));
A327161(n) = length(A327161aux(n,Set([])));

a(n) >= max(A318882(n), 1+A326195(n)).

A052106 a(n) = lcm(n, n - phi(n)).

Original entry on oeis.org

0, 2, 3, 4, 5, 12, 7, 8, 9, 30, 11, 24, 13, 56, 105, 16, 17, 36, 19, 60, 63, 132, 23, 48, 25, 182, 27, 112, 29, 330, 31, 32, 429, 306, 385, 72, 37, 380, 195, 120, 41, 210, 43, 264, 315, 552, 47, 96, 49, 150, 969, 364, 53, 108, 165, 224, 399, 870, 59, 660, 61, 992, 189

Offset: 1

Labos Elemer, Jan 20 2000

nonn

See also A009195, A003277, A050384 when totient and cototient give results identical to each other. This sequence is not identical to A009262.

a(n) = n iff n is in A246655. - Ivan Neretin, May 29 2016

			For n=255, phi(n)=128, cototient(255) = 255 - 128 = 127, a(255) = lcm(255,127) = 32385, while A009262(255) = lcm(255,phi(255)) = 128*255 = 32640;
for n=72, phi(72)=24, A051953(72) = 72 - 24 = 48, a(72) = lcm(72,48) = 144, while A009262(72) = lcm(72,24) = 72.

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A000010, A009262, A051953.

Table[LCM[n, n - EulerPhi[n]], {n, 63}] (* Ivan Neretin, May 29 2016 *)

a(n) = lcm(n, A051953(n)).

A058663 a(n) = gcd(n-1, n-phi(n)).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 3, 1, 1, 21, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1

Offset: 1

Labos Elemer, Dec 28 2000

nonn

			For n = 15; n-1 = 14, cototient(15) = 15-phi(15) = 7, a(15) = gcd(14,7) = 7; For most n-s, among others for primes a(n) = 1.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A049559, A051953, A009195.

with(numtheory); A058663:=n->igcd(n-1, n-phi(n)); seq(A058663(n), n=1..100); # Wesley Ivan Hurt, Apr 01 2014

Table[GCD[n - 1, n - EulerPhi[n]], {n, 100}] (* Wesley Ivan Hurt, Apr 01 2014 *)

A058663(n) = gcd(n-1, n-eulerphi(n)); \\ Antti Karttunen, Sep 25 2018

a(n) = gcd(n-1, cototient(n)) = gcd(n-1, A051953(n)).

A073811 Number of common divisors of n and phi(n).

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Aug 13 2002

nonn

Where records occur: 1, 4, 8, 16, 32, 36, 72, 108, 144, 216, 432, 648, 864, ... - David A. Corneth, Oct 21 2017

			For n = 24: phi(n) = 8, Intersection[{1,2,3,4,6,8,12,24},{1,2,4,8}] = {1,2,4,8}, so a(24) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000005, A000010, A009195, A073802, A073808, A073809, A073810.

g1[x_] := Divisors[x] g2[x_] := Divisors[EulerPhi[x]] ncd[x_] := Length[Intersection[g1[x], g2[x]]] Table[ncd[w], {w, 1, 128}]
Table[Length[Intersection[Divisors[n],Divisors[EulerPhi[n]]]],{n,110}] (* Harvey P. Dale, Oct 03 2013 *)
a[n_] := DivisorSigma[0, GCD[n, EulerPhi[n]]]; Array[a, 100] (* Amiram Eldar, Jul 01 2022 *)

A073811(n) = sumdiv(eulerphi(n),d,!(n%d)); \\ Antti Karttunen, Oct 21 2017

a(n) = numdiv(gcd(eulerphi(n), n)) \\ David A. Corneth, Oct 21 2017

;; Implemented literally (naively) after the description. Either:
(define (A073811 n) (length (filter (lambda (d) (zero? (modulo n d))) (divisors (A000010 n)))))
;; Or:
(define (A073811 n) (let ((phn (A000010 n))) (length (filter (lambda (d) (zero? (modulo phn d))) (divisors n)))))
(define (divisors n) (cons 1 (proper-divisors n))) ;; This can be also memoized with definec.
(define (proper-divisors n) (let loop ((k n) (divs (list))) (cond ((= 1 k) divs) ((zero? (modulo n k)) (loop (- k 1) (cons k divs))) (else (loop (- k 1) divs)))))
;; Antti Karttunen, Oct 21 2017

a(n) = Card[Intersection[D[n], D[A000010(n)]]].
a(n) = Sum_{d|n, d|A000010(n)} 1. - Antti Karttunen, Oct 21 2017
a(n) = A000005(A009195(n)). - Antti Karttunen, Oct 21 2017, after David A. Corneth's PARI-program.

A326197 Number of divisors of n that are not reachable from n with any combination of transitions x -> gcd(x,sigma(x)) and x -> gcd(x,phi(x)).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 1, 0, 0, 1, 0, 2, 1, 1, 0, 2, 0, 1, 0, 2, 0, 4, 0, 0, 1, 1, 2, 4, 0, 1, 1, 2, 0, 4, 0, 2, 3, 1, 0, 4, 0, 2, 1, 2, 0, 2, 1, 3, 1, 1, 0, 7, 0, 1, 2, 0, 2, 4, 0, 2, 1, 5, 0, 4, 0, 1, 3, 2, 2, 4, 0, 4, 0, 1, 0, 6, 2, 1, 1, 3, 0, 6, 1, 2, 1, 1, 1, 4, 0, 2, 3, 4, 0, 4, 0, 3, 5

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

It seems that A000961 gives the positions of zeros.

			From n = 12 we can reach any of the following of its 6 divisors: 12 (with an empty combination of transitions), 4 (as A009194(12) = A009195(12) = 4), 2 (as A009195(4) = 2) and 1 (as A009194(4) = 1 = A009194(2) = A009195(2)). Only the divisors 3 and 6 of 12 are not included in the directed acyclic graph formed from those two transitions (see illustration below), thus a(12) = 2.
.
   12
    |
    4
    | \
    |  2
    | /
    1

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000005, A000961, A009194, A009195, A326196.

A326196aux(n,distvals) = { distvals = setunion([n],distvals); if(1==n,distvals, my(a=gcd(n,eulerphi(n)), b=gcd(n,sigma(n))); distvals = A326196aux(a,distvals); if((a==b)||(b==n),distvals, A326196aux(b,distvals))); };
A326196(n) = length(A326196aux(n,Set([])));
A326197(n) = (numdiv(n) - A326196(n));

a(n) = A000005(n) - A326196(n).

A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 66, 68, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84, 86, 88, 90, 92, 93, 94, 96

Offset: 1

Amiram Eldar, Feb 18 2021

nonn

First differs from A080197 at n = 28.
Erdős et al. (2008) proved that the asymptotic density of numbers k such that gcd(k, phi(k)) > (log(log(k)))^u for a real number u > 0 is equal to exp(-gamma) * Integral_{t=u..oo} rho(t) dt, where rho(t) is the Dickman-de Bruijn function and gamma is Euler's constant (A001620). For this sequence u = 1, and therefore its asymptotic density is 1 - exp(-gamma) = 0.43854... (A227242).
There are only 8 cyclic numbers (A003277) in this sequence: 1, 2, 3, 5, 7, 11, 13, 15. All the other terms are in A060679. The first term of A060679 which is not in this sequence is 1622.

			16 is a term since gcd(16, phi(16)) = gcd(16, 8) = 8 > log(log(16)) = 1.0197...
17 is not a term since gcd(17, phi(17)) = gcd(17, 16) = 1 < log(log(17)) = 1.0414...

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Erdős, Florian Luca and Carl Pomerance, On the proportion of numbers coprime to a given integer, in: J.-M. De Koninck, A. Granville and F. Luca (eds.), Anatomy of Integers, AMS, 2008, pp. 47-64.
Wikipedia, Dickman function.

Cf. A000010, A001620, A003277, A009195, A060679, A080130, A227242, A341750.

Select[Range[100], GCD[#, EulerPhi[#]] > Log[Log[#]] &]

isok(k) = (k==1) || (gcd(k, eulerphi(k)) > log(log(k))); \\ Michel Marcus, Feb 19 2021

A052100 a(n) = lcm(n, phi(n), n - phi(n)).

Original entry on oeis.org

0, 2, 6, 4, 20, 12, 42, 8, 18, 60, 110, 24, 156, 168, 840, 16, 272, 36, 342, 120, 252, 660, 506, 48, 100, 1092, 54, 336, 812, 1320, 930, 32, 8580, 2448, 9240, 72, 1332, 3420, 1560, 240, 1640, 420, 1806, 1320, 2520, 6072, 2162, 96, 294, 300, 31008, 2184, 2756

Offset: 1

Labos Elemer, Jan 20 2000

nonn

If n is a power of a prime p, then a(n) = n*(p-1). - Robert Israel, May 20 2015

			For n=72, phi(72)=24, cototient(72)=48, a(72) = lcm(72,24,48) = 144.
For n=255, phi(255)=128, cototient(255)=127, a(255) = lcm(255,128,127) = 4145280.

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A009262.

seq(ilcm(n, numtheory:-phi(n),n - numtheory:-phi(n)), n=1..100); # Robert Israel, May 20 2015

Table[LCM[n, EulerPhi[n], n - EulerPhi[n]], {n, 53}] (* Ivan Neretin, May 20 2015 *)

a(n) = lcm(n, A000010(n), A051953(n)).
For n=p prime, phi(p)=p-1, cototient(p)=p-1, a(p)=p(p-1)=A009262(p).
a(n) = n*A000010(n)*A051953(n)/A009195(n)^2. - Robert Israel, May 20 2015

A058656 a(n) = gcd(n+1, phi(n)).

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 8, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 12, 1, 2, 3, 8, 1, 2, 1, 2, 5, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 8, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 2, 1, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 2, 1, 2, 1, 2, 1, 2, 3, 8, 1, 2, 1, 4, 1, 2, 1, 24, 1, 2, 3, 20, 1, 2, 1

Offset: 1

Labos Elemer, Dec 28 2000

nonn

Compare sequences gcd(x, phi(n)), where x = n-1, n, or n+1.

			For n = 12, 13, 14, 15: n+1 = 13, 14, 15, 16; phi(n) = 4, 12, 12, 8; a(n) = gcd(13,4), gcd(14,12), gcd(15,12), gcd(16,8) = 1, 2, 3, 8, respectively.

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

Cf. A000010, A009195, A058515.

Table[GCD[n+1,EulerPhi[n]],{n,110}] (* Harvey P. Dale, Nov 17 2011 *)

a(n) = gcd(n+1, eulerphi(n)); \\ Amiram Eldar, Mar 13 2025

Offset corrected by Sean A. Irvine, Aug 11 2022

A058665 a(n) = gcd(n+1, n-phi(n)).

Original entry on oeis.org

2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1

Offset: 1

Labos Elemer, Dec 28 2000

nonn

a(n) = 1 for most n. True for all primes and other integers.

			n = 247 = 13*19, n+1 = 248 = 8*31, phi(247) = 12*18 = 216, cototient(247) = 247-216 = 31, so a(247) = gcd(248,31) = 31.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A009195.

Table[GCD[n+1,n-EulerPhi[n]],{n,0,110}] (* Harvey P. Dale, Dec 24 2012 *)

A058665(n) = gcd(n+1, n-eulerphi(n)); \\ Antti Karttunen, Jul 28 2017

from sympy import gcd, totient
def a(n): return gcd(n + 1, n - totient(n))
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 29 2017

a(n) = gcd(n+1, cototient(n)) = gcd(n+1, A051953(n)).

Offset corrected by Antti Karttunen, Jul 28 2017

A062789 a(n) = gcd(n, phi(n) * (phi(n) + 1)).

Original entry on oeis.org

1, 2, 3, 2, 5, 6, 7, 4, 3, 10, 11, 4, 13, 14, 3, 8, 17, 6, 19, 4, 3, 22, 23, 24, 5, 26, 9, 4, 29, 6, 31, 16, 3, 34, 5, 12, 37, 38, 3, 8, 41, 6, 43, 4, 15, 46, 47, 16, 7, 10, 3, 4, 53, 18, 5, 8, 3, 58, 59, 4, 61, 62, 9, 32, 1, 6, 67, 4, 3, 10, 71, 24, 73, 74, 5, 4, 1, 6, 79, 16, 27, 82, 83, 12

Offset: 1

Reinhard Zumkeller, Jul 19 2001

Harry J. Smith, Table of n, a(n) for n = 1..2000

Cf. A009195, A000010, A039649.

a062789 n = gcd n (phi * (phi + 1)) where phi = a000010 n
-- Reinhard Zumkeller, Oct 07 2015

Table[GCD[n, EulerPhi[n]*(EulerPhi[n] + 1)], {n, 75}] (* Stefan Steinerberger, Apr 03 2006 *)
ep[n_]:=Module[{epn=EulerPhi[n]},GCD[n,epn(epn+1)]]; Array[ep,90] (* Harvey P. Dale, Jun 23 2011 *)

for (n=1, 2000, p=eulerphi(n); write("b062789.txt", n, " ", gcd(n, p*(p + 1)))) \\ Harry J. Smith, Aug 11 2009

More terms from Stefan Steinerberger, Apr 03 2006

More terms from Harry J. Smith, Aug 11 2009

cp's OEIS Frontend

A327161 Number of positive integers that are reachable from n with some combination of transitions x -> usigma(x)-x and x -> gcd(x,phi(x)), where usigma is the sum of unitary divisors of n (A034448), and phi is Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A052106 a(n) = lcm(n, n - phi(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A058663 a(n) = gcd(n-1, n-phi(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A073811 Number of common divisors of n and phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Scheme

Formula

A326197 Number of divisors of n that are not reachable from n with any combination of transitions x -> gcd(x,sigma(x)) and x -> gcd(x,phi(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A052100 a(n) = lcm(n, phi(n), n - phi(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs