cp's OEIS Frontend

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

%I A371924 #24 Apr 28 2024 11:31:32
%S A371924 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,
%T A371924 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,
%U A371924 10,131,67,9,23,7,47,73,17,31,13,79,11,7,173,29,11
%N A371924 a(n) is the least b such that prime(n)-1 divides b!.
%C A371924 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).
%H A371924 Samuel Harkness, <a href="/A371924/b371924.txt">Table of n, a(n) for n = 1..10000</a>
%H A371924 Wikipedia, <a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">Pollard's p-1 algorithm</a>
%e A371924 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.
%t A371924 a371924[p_] :=
%t A371924  Module[{a, d, f, u, v}, f = FactorInteger[p - 1]; d = {};
%t A371924   For[a = 1, a <= Length[f], a++,
%t A371924    u = f[[a]];
%t A371924    v = u[[1]]^u[[2]];
%t A371924    i = 1;
%t A371924    While[! Divisible[(u[[1]]*i)!, v], i++]; AppendTo[d, u[[1]]*i]];
%t A371924   Return[Max[d]]]
%t A371924 list = {};
%t A371924 For[p = 1, p <= 71, p++,
%t A371924  AppendTo[list, {p, a371924[Prime[p]]}]]
%t A371924 Print[list]
%o A371924 (PARI) a(n) = my(b=1, q=prime(n)-1); while (b! % q, b++); b; \\ _Michel Marcus_, Apr 15 2024
%o A371924 (Python)
%o A371924 from sympy import prime
%o A371924 def A371924(n):
%o A371924     m = prime(n)-1
%o A371924     b, k = 1, 1%m
%o A371924     while k:
%o A371924         b += 1
%o A371924         k = k*b%m
%o A371924     return b # _Chai Wah Wu_, Apr 25 2024
%Y A371924 Cf. A000040, A002034, A023503, A092965.
%K A371924 nonn
%O A371924 1,2
%A A371924 _Samuel Harkness_, Apr 12 2024