A068494 -id:A068494 - cp's OEIS frontend

A270096 Smallest m such that 2^m == 2^n (mod n).

0, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 4, 5, 2, 9, 4, 1, 2, 1, 5, 3, 2, 11, 6, 1, 2, 3, 4, 1, 6, 1, 4, 9, 2, 1, 4, 7, 10, 3, 4, 1, 18, 15, 5, 3, 2, 1, 4, 1, 2, 3, 6, 5, 6, 1, 4, 3, 10, 1, 6, 1, 2, 15, 4, 17, 6, 1, 4

Offset: 1

Thomas Ordowski, Mar 11 2016

nonn

a(n) = 1 iff n is a prime or a pseudoprime (odd or even) to base 2.
We have a(n) <= n - phi(n) and a(n) <= phi(n), so a(n) <= n/2.
From Robert Israel, Mar 11 2016: (Start)
If n is in A167791, then a(n) = A068494(n).
If n is odd, a(n) = n mod A002326((n-1)/2).
a(n) >= A007814(n).
a(p^k) = p^(k-1) for all k >= 1 and all odd primes p not in A001220.
Conjecture: a(n) <= n/3 for all n > 8. (End)

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A001220, A002326, A007814, A051953, A068494, A167791.

Cf. A276976 (a generalization on all integer bases).

f:= proc(n) local d,b,t, m,c;
  d:= padic:-ordp(n,2);
  b:= n/2^d;
  t:= 2 &^ n mod n;
  m:= numtheory:-mlog(t,2,b,c);
  if m < d then m:= m + c*ceil((d-m)/c) fi;
  m
end proc:
f(1):= 0:
map(f, [$1..1000]; # Robert Israel, Mar 11 2016

Table[k = 0; While[PowerMod[2, n, n] != PowerMod[2, k, n], k++]; k, {n, 120}] (* Michael De Vlieger, Mar 15 2016 *)

a(n) = {my(m = 0); while (Mod(2, n)^m != 2^n, m++); m; } \\ Altug Alkan, Sep 23 2016

a(n) < n/2 for n > 4.
a(2^k) = k for all k >= 0.
a(2*p) = 2 for all primes p.

More terms from Michel Marcus, Mar 11 2016

A219175 a(n) = n mod lambda(n) where lambda is the Carmichael function (A002322).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 2, 3, 0, 1, 0, 1, 0, 3, 2, 1, 0, 5, 2, 9, 4, 1, 2, 1, 0, 3, 2, 11, 0, 1, 2, 3, 0, 1, 0, 1, 4, 9, 2, 1, 0, 7, 10, 3, 4, 1, 0, 15, 2, 3, 2, 1, 0, 1, 2, 3, 0, 5, 6, 1, 4, 3, 10, 1, 0, 1, 2, 15, 4, 17, 6, 1, 0, 27, 2, 1, 0, 5

Offset: 1

Michel Lagneau, Nov 13 2012

nonn

a(n) = A068494(n) for n = 1..14.
a(k) = 1 for k = prime(n) > 2 or k = A002997(n).
a(n) is the smallest k >= 0 such that b^(n-k) == 1 (mod n) for every b coprime to n. - Thomas Ordowski, Jun 30 2017

			a(9) = 3 because lambda(9) = 6 and 9 == 3 mod 6.

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A068494, A002322, A002997.

with(numtheory):for n from 1 to 100 do: x:=irem(n,lambda(n)): printf(`%d, `,x):od:

Table[Mod[n, CarmichaelLambda[n]], {n, 100}] (* T. D. Noe, Nov 13 2012 *)

a(n)=n%lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Nov 13 2012

A215486 n - 1 mod phi(n), where phi(n) is Euler's totient function.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 3, 0, 1, 6, 7, 0, 5, 0, 3, 8, 1, 0, 7, 4, 1, 8, 3, 0, 5, 0, 15, 12, 1, 10, 11, 0, 1, 14, 7, 0, 5, 0, 3, 20, 1, 0, 15, 6, 9, 18, 3, 0, 17, 14, 7, 20, 1, 0, 11, 0, 1, 26, 31, 16, 5, 0, 3, 24, 21, 0, 23, 0, 1, 34, 3, 16, 5, 0, 15, 26, 1, 0, 11, 20, 1, 30, 7, 0, 17

Offset: 1

Alonso del Arte, Feb 17 2013, based on an idea from Balarka Sen

Lehmer conjectured that a(n) = 0 only when n is 1 or prime.

			a(8) = 3 because 8 - 1 mod phi(8) = 3.
a(9) = 2 because 9 - 1 mod phi(9) = 2.
a(10) = 1 because 10 - 1 mod phi(10) = 1.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Wikipedia, Lehmer's totient problem

Cf. A068494, A007694.

[(n-1) mod EulerPhi(n): n in [2..90]]; // Bruno Berselli, Feb 18 2013

Table[Mod[n - 1, EulerPhi[n]], {n, 2, 100}]

makelist(mod(n-1,totient(n)), n, 2, 90); /* Bruno Berselli, Feb 18 2013 */

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

A327295 Numbers k such that e(k) > 1 and k == e(k) (mod lambda(k)), where e(k) = A051903(k) is the maximal exponent in prime factorization of k.

Original entry on oeis.org

4, 12, 16, 48, 80, 112, 132, 208, 240, 1104, 1456, 1892, 2128, 4144, 5852, 12208, 17292, 18544, 21424, 25456, 30160, 45904, 78736, 97552, 106384, 138864, 153596, 154960, 160528, 289772, 311920, 321904, 399212, 430652, 545584, 750064, 770704, 979916, 1037040, 1058512

Offset: 1

Thomas Ordowski, Dec 05 2019

nonn

The condition e(k) > 1 excludes primes and Carmichael numbers.
Numbers n such that e(k) > 1 and b^k == b^e(k) (mod k) for all b.
These are numbers k such that A276976(k) = e(k) > 1.
Are there infinitely many such numbers? Are all such numbers even?
A number k is a term if and only if k is e(k)-Knödel number with e(k) > 1. So they may have the name nonsquarefree e(k)-Knodel numbers k.
It seems that if k is in this sequence, then e(k) = A007814(k) and k/2^e(k) is squarefree.
Conjecture: there are no composite numbers m > 4 such that m == e(m) (mod phi(m)). By Lehmer's totient conjecture, there are no such squarefree numbers.
Problem: are there odd numbers n such that e(n) > 1 and n == e(n) (mod ord_{n}(2)), where ord_{n}(2) = A002326((n-1)/2)? These are odd numbers n such that 2^n == 2^e(n) (mod n) with e(n) > 1.
Numbers k for which A051903(k) > 1 and A219175(k) = A329885(k). - Antti Karttunen, Dec 11 2019

			The number 4 = 2^2 is a term, because e(4) = A051903(4) = 2 > 1 and 4 == 2 (mod lambda(4)), where lambda(4) = A002322(4) = 2.

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

Cf. A000010, A002322, A002326, A002997, A050990, A050992, A051903, A068494, A219175, A270096, A276976, A324050, A327979, A329885.

A proper subset of A013929.

Select[Range[10^5], (e = Max @@ Last /@ FactorInteger[#]) > 1 && Divisible[# -e, CarmichaelLambda[#]] &] (* Amiram Eldar, Dec 05 2019 *)

isok(n) = ! issquarefree(n) && (Mod(n, lcm(znstar(n)[2])) == vecmax(factor(n)[, 2])); \\ Michel Marcus, Dec 05 2019

More terms from Amiram Eldar, Dec 05 2019

A072303 Numbers n for which n is congruent to n^2 mod phi(n).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 16, 17, 18, 19, 21, 23, 24, 25, 27, 28, 29, 31, 32, 36, 37, 41, 43, 47, 48, 49, 53, 54, 59, 61, 64, 67, 71, 72, 73, 79, 81, 83, 89, 96, 97, 101, 103, 107, 108, 109, 112, 113, 121, 125, 127, 128, 131, 137, 139, 144, 149, 151, 157

Offset: 1

Igor Naverniouk (igor(AT)lexansoft.com), Jul 14 2002

Or, numbers n such that phi(n) divides n*(n-1). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Apr 14 2006

			9 is in the sequence because phi(9) = 6. 9 % 6 = 3 and 9^2 % 6 = 3. But 10 is not in the sequence because phi(10) = 4 and 10 % 4 = 6 and 10^2 % 4 = 0.

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

Cf. A000010, A068494.

isok(n) = ((n^2 - n) % eulerphi(n)) == 0 \\ Michel Marcus, Jun 07 2013

A213514 For composite n, remainder of n - 1 when divided by phi(n), where phi(n) is the totient function (A000010).

Original entry on oeis.org

1, 1, 3, 2, 1, 3, 1, 6, 7, 5, 3, 8, 1, 7, 4, 1, 8, 3, 5, 15, 12, 1, 10, 11, 1, 14, 7, 5, 3, 20, 1, 15, 6, 9, 18, 3, 17, 14, 7, 20, 1, 11, 1, 26, 31, 16, 5, 3, 24, 21, 23, 1, 34, 3, 16, 5, 15, 26, 1, 11, 20, 1, 30, 7, 17, 18, 3, 32, 1, 22, 31, 13, 38, 19, 5, 7, 8, 1, 35, 29, 38, 15, 5, 26, 3, 44, 1, 22, 23, 10

Offset: 1

Balarka Sen, Feb 15 2013

D. Lehmer conjectured that a(k) is never 0. He proved that if such k exists, the corresponding composite n must be odd, squarefree, and divisible by at least 7 primes. Cohen and Haggis showed that such n must be larger than 10^20 and have at least 14 prime factors.

			a(1) = 1 because the first composite number is 4 and 4 - 1 = 1 mod phi(4).
a(2) = 1 because the second composite is 6 and 6 - 1 = 1 mod phi(6).
a(3) = 3 because the third composite is 8 and 8 - 1 = 3 mod phi(8).

Balarka Sen, Table of n, a(n) for n = 1..999
Eric W. Weisstein, Totient Function (MathWorld)
Wikipedia, Euler's totient function

Cf. A000010, A068494, A215486.

DeleteCases[Table[Mod[n - 1, EulerPhi[n]] - Boole[PrimeQ[n]], {n, 100}], -1] (* Alonso del Arte, Feb 15 2013 *)
Mod[#-1,EulerPhi[#]]&/@Select[Range[200],CompositeQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Apr 14 2019 *)

for(n=1,300,if(isprime(n)==0,print1((n-1)%eulerphi(n)",")))

forcomposite(n=4,100,print1((n-1)%eulerphi(n)", ")) \\ Charles R Greathouse IV, Feb 19 2013

A234642 Smallest x such that x mod phi(x) = n, or 0 if no such x exists.

Original entry on oeis.org

1, 3, 10, 9, 20, 25, 30, 15, 40, 21, 50, 35, 60, 33, 98, 39, 80, 65, 90, 51, 100, 45, 70, 95, 120, 69, 338, 63, 196, 161, 110, 87, 160, 93, 130, 75, 180, 217, 182, 99, 200, 185, 170, 123, 140, 117, 190, 215, 240, 141, 250, 235, 676, 329, 230, 159, 392, 153, 322

Offset: 0

Charles R Greathouse IV, Dec 28 2013

Conjecture: a(n) > 0 for all n. This would follow from a form of Goldbach's (binary) conjecture. Checked up to 10^7; largest term in that range is a(9972987) = 4178506411.
Pomerance proves that x = n (mod phi(x)) has at least two solutions for each n, but this allows x < n and so does not prove the conjecture above.
a(n) > 0 for all n <= 10^9. The largest term in that range is a(990429171) = 1050844225771. - Donovan Johnson, Feb 18 2014

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Carl Pomerance, On the congruences σ(n) ≡ a (mod n) and n ≡ a (mod φ(n)), Acta Arithmetica 26:3 (1974-1975), pp. 265-272.

Cf. A068494, A076495.

A234642[n_]:=NestWhile[# + 1 &, 1, Not[Mod[#, EulerPhi[#]] == n] &] (* JungHwan Min, Dec 23 2015 *)
A234642[n_]:=Catch[Do[If[Mod[k, EulerPhi[k]] == n, Throw[k]], {k, Infinity}]] (* JungHwan Min, Dec 23 2015 *)
xmp[n_]:=Module[{x=1},While[Mod[x,EulerPhi[x]]!=n,x++];x]; Array[xmp,60,0] (* Harvey P. Dale, Jan 04 2016 *)

a(n)=my(k=n);while(k++%eulerphi(k)!=n,);k

A253628 Psi(n) mod n, where Psi is the Dedekind psi function (A001615).

Original entry on oeis.org

0, 1, 1, 2, 1, 0, 1, 4, 3, 8, 1, 0, 1, 10, 9, 8, 1, 0, 1, 16, 11, 14, 1, 0, 5, 16, 9, 20, 1, 12, 1, 16, 15, 20, 13, 0, 1, 22, 17, 32, 1, 12, 1, 28, 27, 26, 1, 0, 7, 40, 21, 32, 1, 0, 17, 40, 23, 32, 1, 24, 1, 34, 33, 32, 19, 12, 1, 40, 27, 4, 1, 0, 1, 40, 45

Offset: 1

Tom Edgar, Jan 06 2015

nonn

a(n) = A054024(n) when n is squarefree.
Indices of 1 appear to be given by primes A000040 (see conjecture in A068494). The (weaker) statement that a(prime(i)) = 1 is a direct consequence of the multiplicity of A001615.
a(n) = 0 if n is a member of A187778.

			A001615(12) = 24 and 24 == 0 (mod 12) so a(12) = 0.
A001615(15) = 24 and 24 == 9 (mod 15) so a(15) = 9.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A001615, A068494, A054024, A006093, A187778.

A253628 := proc(n)
    modp(A001615(n),n) ;
end proc: # R. J. Mathar, Jan 09 2015

a253628[n_] :=
Mod[DirichletConvolve[j, MoebiusMu[j]^2, j, #], #] & /@ Range@n; a253628[75] (* Michael De Vlieger, Jan 07 2015, after Jan Mangaldan at A001615 *)

[(n*mul(1+1/p for p in prime_divisors(n)))%n for n in [1..100]]

a(n) = A001615(n) mod n.

A290184 Numbers k such that k mod phi(k) = lambda(k).

Original entry on oeis.org

20, 42, 100, 156, 272, 294, 342, 500, 660, 780, 1332, 1980, 2028, 2058, 2500, 3900, 4624, 5256, 5940, 6498, 7260, 9312, 10140, 11772, 12500, 14406, 17820, 19500, 21780, 26364, 26406, 37056, 49284, 50700, 53460, 62244, 62500, 65340, 65792, 78608, 79860, 97500

Offset: 1

Thomas Ordowski, Jul 23 2017

nonn

Numbers k such that A068494(k) = A002322(k).
If k is in the sequence, then k*gpf(k) is in the sequence.
Are there infinitely many terms of the form (p-1)*p, where p is a prime?

Robert Israel, Table of n, a(n) for n = 1..184

Subsequence of A124240.

Cf. A000010, A002322, A068494.

select(n -> n mod numtheory:-phi(n) = numtheory:-lambda(n), [seq(i,i=2..100000,2)]); # Robert Israel, Aug 04 2017

Select[Range[10^5], Mod[#, EulerPhi@ #] == CarmichaelLambda@ # &] (* Michael De Vlieger, Jul 23 2017 *)

isok(n) = (n % eulerphi(n)) == lcm(znstar(n)[2]); \\ Michel Marcus, Jul 23 2017

More terms from Robert Israel, Jul 23 2017

cp's OEIS Frontend

A270096 Smallest m such that 2^m == 2^n (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A219175 a(n) = n mod lambda(n) where lambda is the Carmichael function (A002322).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A215486 n - 1 mod phi(n), where phi(n) is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

A327295 Numbers k such that e(k) > 1 and k == e(k) (mod lambda(k)), where e(k) = A051903(k) is the maximal exponent in prime factorization of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A072303 Numbers n for which n is congruent to n^2 mod phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A213514 For composite n, remainder of n - 1 when divided by phi(n), where phi(n) is the totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A234642 Smallest x such that x mod phi(x) = n, or 0 if no such x exists.

Views

Author

Keywords

Comments

Links

Crossrefs