A276976 -id:A276976 - cp's OEIS frontend

A290960 Numbers k such that A276976(k) > A270096(k).

8, 32, 56, 64, 96, 128, 144, 155, 170, 176, 192, 196, 204, 215, 221, 224, 238, 248, 255, 256, 272, 288, 320, 322, 336, 341, 352, 368, 372, 374, 384, 432, 448, 465, 476, 496, 510, 512, 527, 544, 574, 576, 608, 612, 623, 635, 640, 644, 645, 658, 663, 672, 682, 697, 704, 714, 731, 736, 744

Offset: 1

Altug Alkan, Aug 15 2017, following a suggestion from N. J. A. Sloane

nonn

Odd terms are 155, 215, 221, 255, 341, 465, 527, 623, 635, 645, 663, ...

These odd terms are odd numbers k such that (k mod A002322(k)) > (k mod A002326((k-1)/2)). - Amiram Eldar and Thomas Ordowski, Nov 28 2019

			8 is a term because A276976(8) = 4 while A270096(8) = 3.

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

Cf. A002322, A002326, A270096, A276976.

A270096:= 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:
A270096(1):= 0:
A276976:= proc(n) local lambda;
  lambda:= numtheory:-lambda(n);
  if n mod lambda = 0 then lambda
  elif n mod 8 = 0 and (n-2) mod lambda = 0 then lambda+2
  else n mod lambda
  fi
end proc:
A276976(1):= 0:
A276976(8):= 4:
A276976(24):= 4:
select(n -> A276976(n) > A270096(n), [$1..1000]); # Robert Israel, Aug 16 2017

With[{nn = 750}, Select[Range@ nn, Function[n, SelectFirst[Range[nn/4 + 10], Function[m, AllTrue[Range[2, n - 1], PowerMod[#, m , n] == PowerMod[#, n , n] &]]] > SelectFirst[Range[nn/4 + 10], PowerMod[2, n, n] == PowerMod[2, #, n] &]]]] (* Michael De Vlieger, Aug 15 2017 *)

A307590 a(n) is the smallest base b such that q = b^n - b^m + 1 is prime, where m = A276976(n).

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 5, 2, 4, 2, 2, 2, 8, 2, 2, 3, 2, 14, 11, 2, 11, 29, 11, 5, 19, 14, 6, 27, 2, 3, 21, 8, 7, 10, 3, 4, 2, 14, 3, 5, 106, 3, 2, 44, 4, 3, 43, 4, 4, 21, 6, 16, 25, 41, 3, 12, 14, 10, 2, 3, 81, 28, 27, 66, 37, 17, 61, 5, 22, 12, 179, 197, 49, 2, 132, 178, 11

Offset: 1

Thomas Ordowski, Apr 19 2019

nonn

If p is a prime, then a(p) is the smallest base b such that q = b^p - b + 1 is prime. These primes q == 1 (mod p) by Fermat's Little Theorem. Note that if p is a prime, then a(p) = 2 if and only if 2^p - 1 is prime, so p is a Mersenne exponent in A000043. Composite numbers n such that a(n) = 2 are 4, 6, 8, 10, 12, 14, 16, 22, 39, 45, 76, ... Cf. composite terms in A307625. Except 8, are these the same numbers?

a(80) does not exist because A276976(80) = 4 and b^8-b^4+1 is a factor of b^80-b^4+1. Similarly, a(n) also does not exist for n = 84, 160, 312, 320, 400, 588, 640, 684, 800, ... - Giovanni Resta, Apr 24 2019

			a(9) = 5 so the number 5^9 - 5^3 + 1 is a prime q == 1 (mod 9).

Cf. A000043, A276976, A307625.

fQ[n_, m_] := AllTrue[Range[2, n - 1], PowerMod[#, m, n] == PowerMod[#, n, n] &]; f[1] = 0; f[2] = 1; f[n_] := Module[{m = 0}, While[!fQ[n, m], m++]; m]; a[n_] := Module[{b = 2, m = f[n]}, While[!PrimeQ[b^n - b^m + 1], b++]; b]; Array[a, 79] (* Amiram Eldar, Apr 19 2019 *)

a276976(n)=if(n<3, return(n-1)); forstep(m=1, n, n%2+1, for(b=0, n-1, if(Mod(b, n)^m-Mod(b, n)^n, next(2))); return(m)); \\ A276976
a(n) = my(b=2); while (!isprime(b^n - b^a276976(n) + 1), b++); b; \\ Michel Marcus, Apr 21 2019

q == 1 (mod n).

More terms from Amiram Eldar, Apr 19 2019

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

Original entry on oeis.org

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

A277127 a(n) = n - lambda(n), where lambda(n) = A002322(n).

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 6, 3, 6, 1, 10, 1, 8, 11, 12, 1, 12, 1, 16, 15, 12, 1, 22, 5, 14, 9, 22, 1, 26, 1, 24, 23, 18, 23, 30, 1, 20, 27, 36, 1, 36, 1, 34, 33, 24, 1, 44, 7, 30, 35, 40, 1, 36, 35, 50, 39, 30, 1, 56, 1, 32, 57, 48, 53, 56, 1, 52, 47, 58, 1, 66, 1, 38, 55, 58, 47, 66, 1, 76, 27, 42, 1

Offset: 1

Thomas Ordowski, Oct 01 2016

nonn

Largest m < n such that b^m == b^n (mod n) for every integer b.

Altug Alkan, Table of n, a(n) for n = 1..10000

Cf. A002322, A033948, A051953, A276976.

Table[n - CarmichaelLambda@ n, {n, 83}] (* Michael De Vlieger, Oct 01 2016 *)

a(n) = n - lcm(znstar(n)[2]); \\ Altug Alkan, Oct 01 2016

a(p) = 1 for prime p.
a(p^2) = p prime.
a(n) = A051953(n) for n in A033948.

More terms from Altug Alkan, Oct 01 2016

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

A330342 a(n) is the smallest k such that b^(n-1) == b^k (mod n) for all integers b.

Original entry on oeis.org

0, 1, 2, 3, 4, 1, 6, 3, 2, 1, 10, 3, 12, 1, 2, 7, 16, 5, 18, 3, 2, 1, 22, 3, 4, 1, 8, 3, 28, 1, 30, 7, 2, 1, 10, 5, 36, 1, 2, 3, 40, 5, 42, 3, 8, 1, 46, 7, 6, 9, 2, 3, 52, 17, 14, 7, 2, 1, 58, 3, 60, 1, 2, 15, 4, 5, 66, 3, 2, 9, 70, 5, 72, 1, 14, 3, 16, 5, 78, 7, 26, 1, 82, 5, 4, 1, 2, 7, 88, 5

Offset: 1

Thomas Ordowski, Dec 11 2019

nonn

Note that (n-1) == a(n) (mod lambda(n)), where lambda(n) = A002322(n).
For n > 1, a(n) = lambda(n) if and only if n is a prime or a Carmichael number. For n <> 1 and 4, a(n) = n-1 if and only if n is a prime.
For n > 2, a(n) = 1 if and only if n is a squarefree 2-Knodel number.
For n > 3, a(n) = 2 if and only if n is a 3-Knodel number.

Cf. A000040, A002997, A002322, A033553, A050990, A051903, A276976.

a[n_] := Module[{k = 0}, While[!AllTrue[Range[n], PowerMod[#, n - 1, n] == PowerMod[#, k, n] &], k++]; k]; Array[a, 100] (* Amiram Eldar, Dec 11 2019 *)

a(n) = A(n) if A(n) >= A051903(n) or a(n) = A002322(n) + A(n) otherwise, where A(n) = ((n-1) mod A002322(n)).

More terms from Amiram Eldar, Dec 11 2019

cp's OEIS Frontend

A290960 Numbers k such that A276976(k) > A270096(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A307590 a(n) is the smallest base b such that q = b^n - b^m + 1 is prime, where m = A276976(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A277127 a(n) = n - lambda(n), where lambda(n) = A002322(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A330342 a(n) is the smallest k such that b^(n-1) == b^k (mod n) for all integers b.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions