A050990 -id:A050990 - cp's OEIS frontend

A208156 8-Knödel numbers.

12, 14, 16, 20, 24, 32, 40, 48, 56, 60, 80, 88, 96, 104, 120, 136, 140, 152, 160, 184, 224, 232, 240, 248, 260, 296, 308, 328, 344, 376, 408, 416, 424, 472, 480, 488, 528, 536, 560, 568, 584, 632, 664, 680, 712, 728, 776, 808, 824, 856, 872, 904, 1016, 1040

Offset: 1

Paolo P. Lava, Feb 24 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Knödel Numbers

Cf. A002997, A050990, A033553, A050992, A050993, A208154, A208155, A208157, A208158.

with(numtheory);
knodel:=proc(i,k)
local a,n,ok;
for n from k+1 to i do
  ok:=1;
  for a from 1 to n do
     if gcd(a,n)=1 then  if (a^(n-k) mod n)<>1 then ok:=0; break; fi; fi;
  od;
  if ok=1 then print(n); fi;
od;
end:
knodel(10000,8)

Select[Range[10, 2000, 2], Divisible[# - 8, CarmichaelLambda[#]]&] (* Jean-François Alcover, Mar 01 2018 *)

A276976 Smallest m such that b^m == b^n (mod n) for every integer b.

Original entry on oeis.org

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

Offset: 1

Thomas Ordowski, Sep 23 2016

It suffices to check all bases 0 < b < n for n > 2.
The congruence n == a(n) (mod A002322(n)) is always true.
a(n) = 1 iff n is a prime or a Carmichael number.
We have a(n) > 0 for n > 1, and a(n) <= n/2.
If n > 2 then a(n) is odd iff n is odd.
Conjecture: a(n) <= n/3 for every n >= 9.
Professor Andrzej Schinzel proved this conjecture (in a letter to the author). - Thomas Ordowski, Sep 30 2016
Note: a(n) = n/3 for n = A038754 >= 3.
Numbers n such that a(n) > A270096(n) are A290960.
Information from Carl Pomerance: a(n) > A002322(n) if and only if 8|n and n is in A050990; such n = 8, 24, 56, ... - Thomas Ordowski, Jun 21 2017
Number of integers k < n such that b^k == b^n (mod n) for every integer b is f(n) = (n - a(n))/lambda(n). For n > 1, f(n) = floor((n-1)/lambda(n)) if and only if a(n) <= lambda(n), where lambda(n) = A002322(n). - Thomas Ordowski, Jun 21 2017
a(n) >= A051903(n); numbers n such that a(n) = A051903(n) are 1, primes, Carmichael numbers, and A327295. - Thomas Ordowski, Dec 06 2019

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

Cf. A002322, A002997, A038754, A050990, A051903, A124240, A219175, A270096, A290960, A327295.

With[{nn = 83}, Table[SelectFirst[Range[nn/4 + 10], Function[m, AllTrue[Range[2, n - 1], PowerMod[#, m , n] == PowerMod[#, n , n] &]]] - Boole[n == 1], {n, nn}]] (* Michael De Vlieger, Aug 15 2017 *)
a[1] = 0; a[8] = a[24] = 4; a[n_] := If[(rem = Mod[n, (lam = CarmichaelLambda[n])]) >= Max @@ Last /@ FactorInteger[n], rem, rem + lam]; Array[a, 100] (* Amiram Eldar, Nov 30 2019 *)

a(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)) \\ Charles R Greathouse IV, Sep 23 2016

def a(n): return next(m for m in range(0, n+1) if all(pow(b,m,n)==pow(b,n,n) for b in range(1, 2*n+1))) # Nicholas Stefan Georgescu, Jun 03 2022

a(p) = 1 for prime p.
a(2*p) = 2 for prime p.
a(3*p) = 3 for odd prime p.
a(p^k) = p^(k-1) for odd prime p and k >= 1.
a(2*p^k) = 2*p^(k-1) for odd prime p and k >= 1.
a(2^k) = 2^(k-2) for k >= 4.
From Thomas Ordowski, Jul 09 2017: (Start)
Full description of the function:
a(n) = lambda(n) if lambda(n)|n except n = 1, 8, and 24;
a(n) = lambda(n)+2 if lambda(n)|(n-2) and 8|n;
a(n) = n mod lambda(n) otherwise;
where lambda(n) = A002322(n). (End)
For n <> 8 and 24, a(n) = A(n) if A(n) >= A051903(n) or a(n) = A002322(n) + A(n) otherwise, where A(n) = A219175(n). - Thomas Ordowski, Nov 30 2019

More terms from Altug Alkan, Sep 23 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

A216090 Numbers n such that k^(n-1) == k (mod n) for every k = 1, 2, ..., n-1.

Original entry on oeis.org

1, 2, 6, 10, 14, 22, 26, 30, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 182, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478, 482

Offset: 1

Michel Lagneau, Sep 01 2012

nonn

Subsequence of, but different from A197930, for example A197930(11) = 42 with 42 distinct residues, but the set R of the residues k^41 mod 42 is R = {1, 32, 33, 16, 17, 6, …, 9, 10, 41} for k = 1, 2, …, 41 instead R = {1, 2, 3, …, 40, 41}. Terms of A197930 that are not in this sequence: 42, 78, 110, 114, 138, 170, …

Squarefree numbers n such that A002322(n) divides n-2. Contains all doubled odd primes and all doubled Carmichael numbers. - Thomas Ordowski, Apr 23 2017

			a(4) = 10 because x^9  == 1, 2, ..., 9  (mod 10) with 9 distinct residues such that:
1^9 = 1 == 1 (mod 10);
2^9 = 512 == 2 (mod 10);
3^9 = 19683 == 3 (mod 10);
4^9 = 262144 == 4 (mod 10);
5^9 = 1953125 == 5 (mod 10);
6^9 = 10077696 == 6 (mod 10);
7^9 = 40353607 == 7 (mod 10);
8^9 = 134217728 == 8 (mod 10);
9^9 = 387420489 == 9 (mod 10).

Paolo P. Lava, Table of n, a(n) for n = 1..1000

Subsequence of A192109.
Terms > 2 form a subsequence of A050990.
Cf. A197929, A197930, A197943.

with(numtheory):for n from 1  to 500 do:j:=0:for i from 1 to n do: if irem(i^(n-1),n)=i then j:=j+1:else fi:od:if j=n-1 then printf(`%d, `, n):else fi:od:

f[n_] := And @@ Table[PowerMod[k, n - 1, n] == k, {k, n - 1}]; Select[Range[500], f] (* T. D. Noe, Sep 03 2012 *)

isok(n) = {for (k=1, n-1, if (Mod(k, n)^(n-1) != Mod(k, n), return (0));); return (1);} \\ Michel Marcus, Apr 23 2017

from sympy.ntheory.factor_ import core
from sympy import primefactors
def ok(n):
    if n<3: return True
    if core(n) == n:
        for p in primefactors(n):
            if (n - 2)%(p - 1): return False
        return True
    return False
print([n for n in range(1, 501) if ok(n)]) # Indranil Ghosh, Apr 23 2017

A265261 Smallest n-Knödel number, i.e., smallest composite c > n such that each b < c coprime to c satisfies b^(c-n) == 1 (mod c).

Original entry on oeis.org

561, 4, 9, 6, 25, 8, 15, 12, 21, 12, 15, 16, 33, 24, 21, 20, 65, 24, 51, 24, 45, 24, 33, 32, 69, 30, 39, 40, 65, 36, 87, 40, 45, 44, 51, 40, 85, 56, 57, 48, 65, 72, 91, 48, 63, 66, 69, 60, 141, 56, 63, 60, 65, 72, 75, 60, 63, 70, 87, 72, 133, 122, 93, 80, 165

Offset: 1

Felix Fröhlich, Apr 06 2016

nonn

Felix Fröhlich, Table of n, a(n) for n = 1..4000
Wikipedia, Knödel number.

Cf. A050990, A033553, A050992, A050993, A208154, A208155, A208156, A208157, A208158.

Table[SelectFirst[Range[n + 1, 10^3], Function[c, CompositeQ@ c && AllTrue[Range[1, c - 1] /. x_ /; ! CoprimeQ[x, c] -> Nothing, Mod[#^(c - n), c] == 1 &]]], {n, 65}] (* Michael De Vlieger, Apr 06 2016, Version 10 *)

a(n) = forcomposite(c=n+1, , my(i=0, j=0); for(b=1, c-1, if(gcd(b, c)==1, i++; if(Mod(b, c)^(c-n)==1, j++))); if(i==j, return(c)))

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

A208156 8-Knödel numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A276976 Smallest m such that b^m == b^n (mod n) for every integer b.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

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

A216090 Numbers n such that k^(n-1) == k (mod n) for every k = 1, 2, ..., n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

A265261 Smallest n-Knödel number, i.e., smallest composite c > n such that each b < c coprime to c satisfies b^(c-n) == 1 (mod c).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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