OFFSET
1,1
COMMENTS
These conditions for k are inspired by the Pollard-Strassen factorization algorithm.
f(i*c) is the product of successive blocks of consecutive integers c*i+1 to c*(i+1) inclusive and can be calculated efficiently mod k by a multi-point polynomial evaluation.
The conditions here are that no g by itself reveals a factor of k (so that the Pollard-Strassen algorithm must examine individual c*i+j terms in some g = k block to find a factor).
LINKS
Mathematics Stack Exchange, Pollard-Strassen algorithm.
Programming Praxis, Strassen's factoring algorithm.
EXAMPLE
For k = 49:
i | c | c*i+1 | c*(i+1) | g
-------------------------------------
1 | 2 | 3 | 4 | 1
2 | 2 | 5 | 6 | 1
Result: 1
For k = 323:
i | c | c*i+1 | c*(i+1) | g
-------------------------------------
1 | 4 | 5 | 8 | 1
2 | 4 | 9 | 12 | 1
3 | 4 | 13 | 16 | 1
4 | 4 | 17 | 20 | 323
Result: 323
PROG
(Python)
from sympy import integer_nthroot, gcd, isprime
def s(k):
c = integer_nthroot(k, 4)[0]
f = [1]*c
for i in range(1, c+1):
for j in range(c*i+1, c*(i+1)+1):
f[i-1] = (f[i-1] * j) % k
f[i-1] = gcd(f[i-1], k)
return f
isok = lambda k: not isprime(k) and not any(k > x > 1 for x in s(k))
print([k for k in range(4, 7200) if isok(k)])
(Python)
from itertools import count, islice
from math import gcd, prod
from sympy import isprime
def A373652_gen(): # generator of terms
for c in count(1):
g = [prod(i*c+j for j in range(1, c+1)) for i in range(1, c+1)]
yield from filter(lambda k: not (k==1 or isprime(k) or any(1<gcd(d, k)<k for d in g)), range(c**4, (c+1)**4))
(PARI) s(n) = my(c=sqrtnint(n, 4), vf = vector(c, k, 1)); for (i=1, #vf, vf[i] = prod(j=c*i+1, c*(i+1), j % n); vf[i] = gcd(vf[i], n); ); vf;
isok(n) = if ((n>1) && !isprime(n), my(x=Set(s(n)), y=Set([1, n])); setunion(x, y) == y); \\ Michel Marcus, Jun 18 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Darío Clavijo, Jun 12 2024
STATUS
approved