A371924 a(n) is the least b such that prime(n)-1 divides b!.

1, 2, 4, 3, 5, 4, 6, 6, 11, 7, 5, 6, 5, 7, 23, 13, 29, 5, 11, 7, 6, 13, 41, 11, 8, 10, 17, 53, 9, 7, 7, 13, 17, 23, 37, 10, 13, 9, 83, 43, 89, 6, 19, 8, 14, 11, 7, 37, 113, 19, 29, 17, 6, 15, 10, 131, 67, 9, 23, 7, 47, 73, 17, 31, 13, 79, 11, 7, 173, 29, 11

Offset

1,2

Comments

This list is connected to Pollard's p-1 algorithm, using the version of the algorithm iterating over all positive integers. Say a large number m has two distinct prime factors q and r, and using Pollard's p-1 algorithm someone wishes to obtain the prime factors. Say q = 223 and r = 307. As prime(48) = 223 and a(48) = 37, given a random "a" coprime to m the factor 223 will be discovered in 37 steps. Also, as prime(63) = 307 and a(63) = 17, given a random "a" coprime to m the factor 307 will be discovered in 17 steps. Note that after 37 steps both factors will be discovered, so the algorithm will return m, failing to discover either prime factor. Therefore, when 17 <= b < 37 the prime factor 307 will be discovered. Note that on rare occasions, for a given "a" value, by chance p divides (a^b! - 1), so it is possible that for some "a" values the actual b value will be less. But, for any "a" value and prime p = prime(n), it is guaranteed that b <= a(n).

Links

Samuel Harkness, Table of n, a(n) for n = 1..10000

Wikipedia, Pollard's p-1 algorithm

Example

For n = 25, prime(25) = 97, so we will use p = 97. Then the prime factorization of p - 1  is p - 1 = 2^5 * 3. Note that for p - 1 to divide b!, the exponents for all prime factors in b! must be greater than or equal to the exponents for all prime factors in the prime factorization of p - 1. We find that 8! = 2^7 * 3^2 * 5 * 7 is the least b such that this is true, so a(25) = 8.

Mathematica

a371924[p_] :=
 Module[{a, d, f, u, v}, f = FactorInteger[p - 1]; d = {};
  For[a = 1, a <= Length[f], a++,
   u = f[[a]];
   v = u[[1]]^u[[2]];
   i = 1;
   While[! Divisible[(u[[1]]*i)!, v], i++]; AppendTo[d, u[[1]]*i]];
  Return[Max[d]]]
list = {};
For[p = 1, p <= 71, p++,
 AppendTo[list, {p, a371924[Prime[p]]}]]
Print[list]

Prog

(PARI) a(n) = my(b=1, q=prime(n)-1); while (b! % q, b++); b; \\ Michel Marcus, Apr 15 2024
(Python)
from sympy import prime
def A371924(n):
    m = prime(n)-1
    b, k = 1, 1%m
    while k:
        b += 1
        k = k*b%m
    return b # Chai Wah Wu, Apr 25 2024

Crossrefs

Cf. A000040, A002034, A023503, A092965.

Sequence in context: A048186 A352196 A060762 * A328793 A195782 A053049

Adjacent sequences: A371921 A371922 A371923 * A371925 A371926 A371927

Keyword

nonn

Author

Samuel Harkness, Apr 12 2024

Status

approved