A009195 -id:A009195 - cp's OEIS frontend

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120, 465, 256, 330, 272, 420, 216, 666, 342, 468, 320, 820, 252, 903, 440, 540, 506, 1081, 384, 1029, 500, 816, 624, 1378, 486, 1100, 672

Offset: 1

Olivier Gérard

Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
a(1) = 1, since 1 is coprime to any positive integer.
Row sums of A038566. - Wolfdieter Lang, May 03 2015
Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - Muhammed Hedayet, May 19 2024

			G.f. = x + x^2 + 3*x^3 + 4*x^4 + 10*x^5 + 6*x^6 + 21*x^7 + 16*x^8 + 27*x^9 + ...
a(12) = 1 + 5 + 7 + 11 = 24.
n = 40: The smallest positive reduced residue system modulo 40 is {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}. The sum is a(40) = 320. Average is 20.

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
David M. Burton, Elementary Number Theory, p. 171.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
John D. Baum, A Number-Theoretic Sum, Mathematics Magazine 55.2 (1982): 111-113.
Geoffrey B. Campbell, Dirichlet summations and products over primes, Int. J. Math. Math. Sci. 16 92) (1993) 359. eq. (3.1)
Muhammed H. Islam and Shahriar Manzoor, φ1 and phitorial are injections, for any positive integer N, where N > 1.
Constantin M. Petridi, The Sums of the k-powers of the Euler set and their connection with Artin's conjecture for primitive roots, arXiv:1612.07632 [math.NT], 2016.
David Zmiaikou, Origamis and permutation groups, Thesis, 2011. See p. 65.

Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.
Row sums of A127368, A144734, A144824.
Cf. A000217, A002618, A008683, A009195, A023022, A065484, A076512, A175505, A175506.

a023896 = sum . a038566_row  -- Reinhard Zumkeller, Mar 04 2012

[1] cat [n*EulerPhi(n)/2: n in [2..70]]; // Vincenzo Librandi, May 16 2015

A023896 := proc(n)
    if n = 1 then
        1;
    else
        n*numtheory[phi](n)/2 ;
    end if;
end proc: # R. J. Mathar, Sep 26 2013

a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* Michael Somos, Jul 08 2014 *)

{a(n) = if(n<2, n>0, n*eulerphi(n)/2)};

A023896(n)=n*eulerphi(n)\/2 \\ about 10% faster. - M. F. Hasler, Feb 01 2021

from sympy import totient
def A023896(n): return 1 if n == 1 else n*totient(n)//2 # Chai Wah Wu, Apr 08 2022

def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
print([A023896(n) for n in range(1, 57)])  # Peter Luschny, Dec 03 2023

a(n) = n*A023022(n) for n > 2.
a(n) = phi(n^2)/2 = n*phi(n)/2 = A002618(n)/2 if n > 1, a(1)=1. See the Apostol reference for this exercise.
a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
If n = p is a prime, a(p) = T(p-1) where T(k) is the k-th triangular number (A000217). - Robert G. Wilson v, Jul 31 2004
Equals A054521 * [1,2,3,...]. - Gary W. Adamson, May 20 2007
a(n) = A053818(n) * A175506(n) / A175505(n). - Jaroslav Krizek, Aug 01 2010
If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - Thomas Ordowski, Nov 09 2014
G.f.: Sum_{n>=1} mu(n)*n*x^n/(1-x^n)^3, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 24 2015
G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - Ilya Gutkovskiy, Sep 06 2019
For n > 1: a(n) = (n*A076512(n)/2)*A009195(n). - Jamie Morken, Dec 16 2019
Sum_{n>=1} 1/a(n) = 2 * A065484 - 1 = 3.407713... . - Amiram Eldar, Oct 09 2023

Typos in programs corrected by Zak Seidov, Aug 03 2010

Name and example edited by Wolfdieter Lang, May 03 2015

A003277 Cyclic numbers: k such that k and phi(k) are relatively prime; also k such that there is just one group of order k, i.e., A000001(k) = 1.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 123, 127, 131, 133, 137, 139, 141, 143, 145, 149, 151, 157, 159, 161, 163, 167, 173

Offset: 1

N. J. A. Sloane and Richard Stanley

Except for a(2)=2, all the terms in the sequence are odd. This is because of the existence of a non-cyclic dihedral group of order 2n for each n>1. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001
Also gcd(n, A051953(n)) = 1. - Labos Elemer
n such that x^n == 1 (mod n) has no solution 2 <= x <= n. - Benoit Cloitre, May 10 2002
There is only one group (the cyclic group of order n) whose order is n. - Gerard P. Michon, Jan 08 2008  [This is a 1947 result of Tibor Szele. - Charles R Greathouse IV, Nov 23 2011]
Any divisor of a Carmichael number (A002997) must be odd and cyclic. Conversely, G. P. Michon conjectured (c. 1980) that any odd cyclic number has at least one Carmichael multiple (if the conjecture is true, each of them has infinitely many such multiples). In 2007, Michon & Crump produced explicit Carmichael multiples of all odd cyclic numbers below 10000 (see link, cf. A253595). - Gerard P. Michon, Jan 08 2008
Numbers n such that phi(n)^phi(n) == 1 (mod n). - Michel Lagneau, Nov 18 2012
Contains A000040, and all members of A006094 except 6. - Robert Israel, Jul 08 2015
Number m such that n^n == r (mod m) is solvable for any r. - David W. Wilson, Oct 01 2015
Numbers m such that A074792(m) = m + 1. - Thomas Ordowski, Jul 16 2017
Squarefree terms of A056867 (see McCarthy link p. 592 and similar comment with "cubefree" in A051532). - Bernard Schott, Mar 24 2022

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
J. S. Rose, A Course on Group Theory, Camb. Univ. Press, 1978, see p. 7.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Max Alekseyev, Michon's conjecture (Open Problem Garden, Aug. 2007).
Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See pp. 1, 2, 30.
Keith Conrad, When are all groups of order n cyclic?, University of Connecticut, 2019.
Peter J. Dukes and Joanna Niezen, Pairwise balanced designs of dimension three, Australasian Journal Of Combinatorics, Volume 61(1) (2015), pages 98-113.
Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78.
Jose M. Grau, Manuel Rodríguez, A. Oller-Marcen, and Daniel Sadornil, Fermat test with gaussian base and Gaussian pseudoprimes, arXiv preprint arXiv:1401.4708 [math.NT], 2014.
Donald J. McCarthy, A survey of partial converses to Lagrange's theorem on finite groups, Transactions of the New York Academy of Sciences, Vol. 33, No. 6, Series II (1971), pp. 586-594. See page 592.
Gérard P. Michon, Carmichael Divisors
Gérard P. Michon and J. K. Crump, Carmichael Multiples of Odd Cyclic Numbers (up to 10000)
Jonathan Pakianathan and Krishnan Shankar, Nilpotent Numbers, Amer. Math. Monthly, 107, August-September 2000, 631-634.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
T. Szele, Über die endlichen Ordnungszahlen, zu denen nur eine Gruppe gehört, Commentarii Mathematici Helvetici 20 (1947), pp. 265-267.
Index entries for sequences related to groups

Subsequence of A051532. Intersection of A056867 and A005117.
Cf. A000010, A008966, A009195, A050384 (the same sequence but with the primes removed). Also A000001(a(n)) = 1.
Cf. A002997, A006094, A054395, A055561, A054396, A054397, A056867, A135850, A249550, A249551, A249552, A249553, A249554, A249555, A036537, A051953, A253595.

import Data.List (elemIndices)
a003277 n = a003277_list !! (n-1)
a003277_list = map (+ 1) $ elemIndices 1 a009195_list
-- Reinhard Zumkeller, Feb 27 2012

[n: n in [1..200] | Gcd(n, EulerPhi(n)) eq 1]; // Vincenzo Librandi, Jul 09 2015

select(t -> igcd(t, numtheory:-phi(t))=1, [$1..1000]); # Robert Israel, Jul 08 2015

Select[Range[175], GCD[#, EulerPhi[#]] == 1 &] (* Jean-François Alcover, Apr 04 2011 *)
Select[Range@175, FiniteGroupCount@# == 1 &] (* Robert G. Wilson v, Feb 16 2017 *)
Select[Range[200],CoprimeQ[#,EulerPhi[#]]&] (* Harvey P. Dale, Apr 10 2022 *)

isA003277(n) = gcd(n,eulerphi(n))==1 \\ Michael B. Porter, Feb 21 2010

# Compare A050384.
def isPrimeTo(n, m): return gcd(n, m) == 1
def isCyclic(n): return isPrimeTo(n, euler_phi(n))
[n for n in (1..173) if isCyclic(n)] # Peter Luschny, Nov 14 2018

n = p_1*p_2*...*p_k (for some k >= 0), where the p_i are distinct primes and no p_j-1 is divisible by any p_i.
A000001(a(n)) = 1.
Erdős proved that a(n) ~ e^gamma n log log log n, where e^gamma is A073004. - Charles R Greathouse IV, Nov 23 2011
A000005(a(n)) = 2^k. - Carlos Eduardo Olivieri, Jul 07 2015
A008966(a(n)) = 1. - Bernard Schott, Mar 24 2022

More terms from Christian G. Bower

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

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 6, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4

Offset: 1

Labos Elemer, Dec 28 2000

nonn

For prime n, a(n) = n - 1. Question: do nonprimes exist with this property?
Answer: No. If n is composite then a(n) < n - 1. - Charles R Greathouse IV, Dec 09 2013
Lehmer's totient problem (1932): are there composite numbers n such that a(n) = phi(n)? - Thomas Ordowski, Nov 08 2015
a(n) = 1 for n in A209211. - Robert Israel, Nov 09 2015

			a(9) = 2 because phi(9) = 6 and gcd(8, 6) = 2.
a(10) = 1 because phi(10) = 4 and gcd(9, 4) = 1.

Richard K. Guy, Unsolved Problems in Number Theory, B37.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Lehmer's Totient Problem

Cf. A000010, A002322, A039766, A063994, A160595, A209211, A219428, A264012, A264024, A280262, A283656, A283872, A284089, A284440, A318827, A318829, A318830, A330747 (ordinal transform), A340195.

Cf. also A009195, A058515, A058663, A187730, A258409, A339964, A340071, A340081, A340087 for more or less analogous sequences.

[Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

seq(igcd(n-1, numtheory:-phi(n)), n=1..100); # Robert Israel, Nov 09 2015

Table[GCD[n - 1, EulerPhi[n]], {n, 93}] (* Michael De Vlieger, Nov 09 2015 *)

a(n)=gcd(eulerphi(n),n-1) \\ Charles R Greathouse IV, Dec 09 2013

from sympy import totient, gcd
print([gcd(totient(n), n - 1) for n in range(1, 101)]) # Indranil Ghosh, Mar 27 2017

a(p^m) = a(p) = p - 1 for prime p and m > 0. - Thomas Ordowski, Dec 10 2013
From Antti Karttunen, Sep 09 2018: (Start)
a(n) = A000010(n) / A160595(n) = A063994(n) / A318829(n).
a(n) = n - A318827(n) = A000010(n) - A318830(n).
(End)
a(n) = gcd(A000010(n), A219428(n)) = gcd(A000010(n), A318830(n)). - Antti Karttunen, Jan 05 2021

A009191 a(n) = gcd(n, d(n)), where d(n) is the number of divisors of n (A000005).

Original entry on oeis.org

1, 2, 1, 1, 1, 2, 1, 4, 3, 2, 1, 6, 1, 2, 1, 1, 1, 6, 1, 2, 1, 2, 1, 8, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 9, 1, 2, 1, 8, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 8, 1, 2, 1, 12, 1, 2, 3, 1, 1, 2, 1, 2, 1, 2, 1, 12, 1, 2, 3, 2, 1, 2, 1, 10, 1, 2, 1, 12, 1, 2, 1, 8, 1, 6, 1, 2, 1, 2, 1, 12, 1, 2, 3, 1, 1, 2, 1, 8, 1

Offset: 1

David W. Wilson

nonn

a(A046642(n)) = 1.
First occurrence of k: 1, 2, 9, 8, 400, 12, 3136, 24, 36, 80, 123904, 60, 692224, 448, 2025, 384, .... Conjecture: each k is present. - Robert G. Wilson v, Mar 27 2013
Conjecture is true. See David A. Corneth's comment in A324553. - Antti Karttunen, Mar 06 2019

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from T. D. Noe)

Cf. A000005, A009194, A009195, A009205, A009213, A009230, A049820, A125168, A138010, A286540, A303781, A318459, A319337, A322979, A322980, A323073.

Cf. A046642 (positions of ones), A324553 (position of the first occurrence of each n).

a009191 n = gcd n $ a000005 n
-- Reinhard Zumkeller, May 09 2013, Aug 14 2011

f[n_] := GCD[n, DivisorSigma[0, n]]; Array[f, 105] (* Robert G. Wilson v, Mar 27 2013 *)

a(n)=gcd(numdiv(n),n) \\ Charles R Greathouse IV, Mar 26 2013

a(n) = gcd(n, A000005(n)) = gcd(n, A049820(n)). - Antti Karttunen, Sep 25 2018

A109395 Denominator of phi(n)/n = Product_{p|n} (1 - 1/p); phi(n)=A000010(n), the Euler totient function.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 15, 2, 17, 3, 19, 5, 7, 11, 23, 3, 5, 13, 3, 7, 29, 15, 31, 2, 33, 17, 35, 3, 37, 19, 13, 5, 41, 7, 43, 11, 15, 23, 47, 3, 7, 5, 51, 13, 53, 3, 11, 7, 19, 29, 59, 15, 61, 31, 7, 2, 65, 33, 67, 17, 69, 35, 71, 3, 73, 37, 15, 19, 77, 13, 79, 5, 3

Offset: 1

Franz Vrabec, Aug 26 2005

a(n)=2 iff n=2^k (k>0); otherwise a(n) is odd. If p is prime, a(p)=p; the converse is false, e.g.: a(15)=15. It is remarkable that this sequence often coincides with A006530, the largest prime P dividing n. Theorem: a(n)=P if and only if for every prime p < P in n there is some prime q in n with p|(q-1). - Franz Vrabec, Aug 30 2005

			a(10) = 10/gcd(10,phi(10)) = 10/gcd(10,4) = 10/2 = 5.

Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms 1..1000 from T. D. Noe)
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A076512 for the numerator.
Cf. A000010, A009195, A054741, A059956, A082695, A318304, A318305, A323170.
Phi(m)/m = k: A000079 \ {1} (k=1/2), A033845 (k=1/3), A000244 \ {1} (k=2/3), A033846 (k=2/5), A000351 \ {1} (k=4/5), A033847 (k=3/7), A033850 (k=4/7), A000420 \ {1} (k=6/7), A033848 (k=5/11), A001020 \ {1} (k=10/11), A288162 (k=6/13), A001022 \ {1} (12/13), A143207 (k=4/15), A033849 (k=8/15), A033851 (k=24/35).

Table[Denominator[EulerPhi[n]/n], {n, 81}] (* Alonso del Arte, Sep 03 2011 *)

a(n)=n/gcd(n,eulerphi(n)) \\ Charles R Greathouse IV, Feb 20 2013

A007947(n) = factorback(factorint(n)[, 1]); \\ From A007947
A173557(n) = my(f=factor(n)[, 1]); prod(k=1, #f, f[k]-1); \\ From A173557
A109395(n) = denominator(A173557(n)/A007947(n)); \\ Antti Karttunen, Feb 09 2019

a(n) = n/gcd(n, phi(n)) = n/A009195(n).
From Antti Karttunen, Feb 09 2019: (Start)
a(n) = denominator of A173557(n)/A007947(n).
a(2^n) = 2 for all n >= 1.
(End)
From Amiram Eldar, Jul 31 2020: (Start)
Asymptotic mean of phi(n)/n: lim_{m->oo} (1/m) * Sum_{n=1..m} A076512(n)/a(n) = 6/Pi^2 (A059956).
Asymptotic mean of n/phi(n): lim_{m->oo} (1/m) * Sum_{n=1..m} a(n)/A076512(n) = zeta(2)*zeta(3)/zeta(6) (A082695). (End)

A076512 Denominator of cototient(n)/totient(n).

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 2, 10, 1, 12, 3, 8, 1, 16, 1, 18, 2, 4, 5, 22, 1, 4, 6, 2, 3, 28, 4, 30, 1, 20, 8, 24, 1, 36, 9, 8, 2, 40, 2, 42, 5, 8, 11, 46, 1, 6, 2, 32, 6, 52, 1, 8, 3, 12, 14, 58, 4, 60, 15, 4, 1, 48, 10, 66, 8, 44, 12, 70, 1, 72, 18, 8, 9, 60, 4, 78, 2, 2, 20, 82, 2, 64, 21

Offset: 1

Reinhard Zumkeller, Oct 15 2002

a(n)=1 iff n=A007694(k) for some k.
Numerator of phi(n)/n=Prod_{p|n} (1-1/p). - Franz Vrabec, Aug 26 2005
From Wolfdieter Lang, May 12 2011: (Start)
For n>=2, a(n)/A109395(n) = sum(((-1)^r)*sigma_r,r=0..M(n)) with the elementary symmetric functions (polynomials) sigma_r of the indeterminates {1/p_1,...,1/p_M(n)} if n = prod((p_j)^e(j),j=1..M(n)) where M(n)=A001221(n) and sigma_0=1.
This follows by expanding the above given product for phi(n)/n.
The n-th member of this rational sequence 1/2, 2/3, 1/2, 4/5, 1/3, 6/7, 1/2, 2/3, 2/5,... is also (2/n^2)*sum(k,with 1<=k=2.
Therefore, this scaled sum depends only on the distinct prime factors of n.
See also A023896. Proof via PIE (principle of inclusion and exclusion). (End)
In the sequence of rationals r(n)=eulerphi(n)/n: 1, 1/2, 2/3, 1/2, 4/5, 1/3, 6/7, 1/2, 2/3, 2/5, 10/11, 1/3, ... one can observe that new values are obtained for squarefree indices (A005117); while for a nonsquarefree number n (A013929), r(n) = r(A007947(n)), where A007947(n) is the squarefree kernel of n. - Michel Marcus, Jul 04 2015

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

Cf. A076511 (numerator of cototient(n)/totient(n)), A051953.

Phi(m)/m = k: A000079 \ {1} (k=1/2), A033845 (k=1/3), A000244 \ {1} (k=2/3), A033846 (k=2/5), A000351 \ {1} (k=4/5), A033847 (k=3/7), A033850 (k=4/7), A000420 \ {1} (k=6/7), A033848 (k=5/11), A001020 \ {1} (k=10/11), A288162 (k=6/13), A001022 \ {1} (12/13), A143207 (k=4/15), A033849 (k=8/15), A033851 (k=24/35).

[Numerator(EulerPhi(n)/n): n in [1..100]]; // Vincenzo Librandi, Jul 04 2015

Table[Denominator[(n - EulerPhi[n])/EulerPhi[n]], {n, 80}] (* Alonso del Arte, May 12 2011 *)

vector(80, n, numerator(eulerphi(n)/n)) \\ Michel Marcus, Jul 04 2015

a(n) = A000010(n)/A009195(n).

A082505 a(n) = sum of (n-1)-th row terms of triangle A134059.

Original entry on oeis.org

0, 1, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472

Offset: 0

Labos Elemer, Apr 28 2003

a(n) is the least number x such that gcd(2^x, x-phi(x)) = 2^n. If cototient is replaced by totient, analogous values are different: A053576.

			G.f. = x + 6*x^2 + 12*x^3 + 24*x^4 + 48*x^5 + 96*x^6 + 192*x^7 + 384*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A000010, A007283, A009195, A050339, A134059.

Essentially the same as A003945 (and perhaps also A058764).

[0, 1] cat [ &+[ 3*Binomial(n,k): k in [0..n] ]: n in [1..30] ]; // Klaus Brockhaus, Dec 02 2009

0,1,seq(3*2^(n-1), n=2..40); # G. C. Greubel, Apr 27 2021

{0}~Join~Map[Total, {{1}}~Join~Table[3 Binomial[n, k], {n, 30}, {k, 0, n}]] (* Michael De Vlieger, Jul 03 2016, after Harvey P. Dale at A134059 *)
Table[3*2^(n-1) -(3/2)*Boole[n==0] -2*Boole[n==1], {n,0,40}] (* G. C. Greubel, Apr 27 2021 *)
Join[{0,1},NestList[2#&,6,30]] (* Harvey P. Dale, Jan 22 2024 *)

{a(n) = local(A); if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (-6*k + 16) * A[k-1] + 2 * sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 23 2011 */

a(n)=if(n<2,n,3<<(n-1)) \\ Charles R Greathouse IV, Jun 16 2012

[0,1]+[3*2^(n-1) for n in (2..40)] # G. C. Greubel, Apr 27 2021

a(n) = A007283(n-1) for n>1, with a(0) = 0 and a(1) = 1.
G.f.: x * (1 + 4*x) / (1 - 2*x) = x / (1 - 6*x / (1 + 4*x)). - Michael Somos, Jun 15 2012
Starting (1, 6, 12, 24, 48, ...) = binomial transform of [1, 5, 1, 5, 1, 5, ...]. - Gary W. Adamson, Nov 18 2007
a(n+1) = Sum_{k=0..n} A109466(n,k)*A144706(k). - Philippe Deléham, Oct 30 2008
a(n) = (-6*n + 16) * a(n-1) + 2 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011
E.g.f.: (-3 - 4*x + 3*exp(2*x))/2. - Ilya Gutkovskiy, Jul 04 2016
a(n) = 3*2^(n-1) - (3/2)*[n=0] - 2*[n=1]. - G. C. Greubel, Apr 27 2021

More terms from Klaus Brockhaus, Dec 02 2009

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

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

Number of distinct vertices in the directed acyclic graph formed by edge relations x -> A009194(x) and x -> A009195(x), where n is the unique root of the graph.
Because both A009194(n) and A009195(n) are divisors of n, it means that any number reached from n must also be a divisor of n. Number n is also included in the count as it is reached with an empty sequence of transitions.
Question: Are there any other numbers than those in A000961 for which a(n) = A000005(n) ?

			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)), thus a(12) = 4.
The directed acyclic graph formed from those two transitions with 12 as its unique root looks like this:
   12
    |
    4
    | \
    |  2
    | /
    1

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

Cf. A000005, A000961, A009194, A009195, A326192, A326194, A326195, A326197.

Cf. also A326189, A326198.

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

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

a(n) > max(A326194(n), A326195(n)).

A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 8, 3, 2, 1, 8, 5, 2, 9, 4, 1, 4, 1, 16, 1, 2, 1, 12, 1, 2, 3, 16, 1, 12, 1, 4, 3, 2, 1, 16, 7, 10, 1, 8, 1, 18, 5, 8, 3, 2, 1, 16, 1, 2, 9, 32, 1, 4, 1, 8, 1, 4, 1, 24, 1, 2, 5, 4, 1, 12, 1, 32, 27, 2, 1, 24, 1, 2, 1, 8, 1, 12, 1, 4, 3

Offset: 1

Benoit Cloitre, Aug 21 2002

More generally, if the equation a(x)*m=x has solutions, solutions are congruent to m: a(x)*7=x for x=7, 14, 21, 28, 49, 56, 63, 98, 112, ... . There are some composite values of m such that a(x)*m=x has solutions, as m=15. a(n) coincides with A009195(n) at many values of n, but not at n = 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, ... . It seems also that for n large enough sum_{k=1..n} a(k) > n*log(n)*log(log(n)).

Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices. - M. F. Hasler, Feb 23 2014

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

1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])),n=2..100); # Robert Israel, Dec 07 2014

f[n_] := (d = If[ OddQ@ n, 1, 2]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = f[2] = 1; Array[f, 93] (* or *)
f[n_] := Length@ Select[ Range@ n, PowerMod[#, n, n] == 1 &]; f[n_] := 1 /; n<2; Array[f, 93] (* Robert G. Wilson v, Dec 06 2014 *)

A072994=n->sum(k=1,n,Mod(k,n)^n==1) \\ M. F. Hasler, Feb 23 2014

For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n-1), a(A065119(n)) = A065119(n)/3.

For n>1, a(A026383(n)) = A026383(n)/5.

Corrected by T. D. Noe, May 19 2007

A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Apr 07 2003

nonn

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

Cf. A000010, A003277, A006530, A009195, A070003.

Cf. also A082062, A082063, A082064, A082065, A082066, A082067.

gcpd := proc(a,b) local g ,d ; g := 1 ; for d in numtheory[divisors](a) intersect numtheory[divisors](b) do if isprime(d) then g := max(g,d) ; end if; end do: g ; end proc:
A082061 := proc(n) gcpd( numtheory[phi](n), n) ; end proc: # R. J. Mathar, Jul 09 2011

(* factors/exponent SET *) ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := x; f2[x_] := EulerPhi[x]; Table[Max[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Max@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
a(n)=gpf(gcd(eulerphi(n),n)) \\ Charles R Greathouse IV, Feb 19 2013

a(n) = A006530(A009195(n)). - Antti Karttunen, Nov 03 2017
From Amiram Eldar, Dec 06 2024: (Start)
a(n) <= A006530(n), with equality if and only if n is in A070003.
a(n) = 1 if and only if n is a cyclic number (A003277). (End)

Changed "was found" to "exists" in definition. - N. J. A. Sloane, Jan 29 2022

cp's OEIS Frontend

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

Extensions

A003277 Cyclic numbers: k such that k and phi(k) are relatively prime; also k such that there is just one group of order k, i.e., A000001(k) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A009191 a(n) = gcd(n, d(n)), where d(n) is the number of divisors of n (A000005).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A109395 Denominator of phi(n)/n = Product_{p|n} (1 - 1/p); phi(n)=A000010(n), the Euler totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A076512 Denominator of cototient(n)/totient(n).