login
A109939
Largest k-digit prime == 1 (mod n) where k is the number of digits in n, or 0 if no such prime exists.
2
0, 7, 7, 5, 0, 7, 0, 0, 0, 71, 89, 97, 79, 71, 61, 97, 0, 73, 0, 61, 43, 89, 47, 97, 0, 79, 0, 29, 59, 61, 0, 97, 67, 0, 71, 73, 0, 0, 79, 41, 83, 43, 0, 89, 0, 47, 0, 97, 0, 0, 0, 53, 0, 0, 0, 0, 0, 59, 0, 61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71, 0, 73, 0, 0, 0, 0
OFFSET
1,2
LINKS
EXAMPLE
There are 2 digits in n=13, and 13*6 + 1 = 79 is the largest 2-digit prime == 1 (mod 13), so a(13) = 79.
MATHEMATICA
lkdp[n_]:=Module[{k=IntegerLength[n]}, SelectFirst[Reverse[Prime[Range[PrimePi[10^(k-1)+1], PrimePi[10^k-1]]]], Mod[#, n]==1&]]/.Missing["NotFound"]->0; Array[lkdp, 80]
PROG
(Python)
from sympy import prime, prevprime
def a(n):
k = len(str(n)); p = prevprime(10**k); lb = max(10**(k-1), 2)
while p > lb and p%n != 1: p = prevprime(p)
return p if p > lb else 0
print([a(n) for n in range(1, 40)]) # Michael S. Branicky, Jul 07 2021
(Python) # faster version for initial segment of sequence
from sympy import prime, primerange
def aupto(limit):
alst, primeswithkdigs = [], dict()
for k in range(1, len(str(limit))+1):
primeswithkdigs[k] = list(primerange(10**(k-1), 10**k))[::-1]
for n in range(1, limit+1):
k, found = len(str(n)), False
for pk in primeswithkdigs[k]:
if pk%n == 1: alst.append(pk); found = True; break
if not found: alst.append(0)
return alst
print(aupto(39)) # Michael S. Branicky, Jul 07 2021
CROSSREFS
Cf. A109938.
Sequence in context: A375190 A081824 A199083 * A053011 A021133 A354238
KEYWORD
base,easy,nonn
AUTHOR
Amarnath Murthy, Jul 19 2005
EXTENSIONS
a(1) and a(4) corrected and a(40) and beyond from Michael S. Branicky, Jul 07 2021
STATUS
approved