A109939 Largest k-digit prime == 1 (mod n) where k is the number of digits in n, or 0 if no such prime exists.

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

Michael S. Branicky, Table of n, a(n) for n = 1..10000

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: A225402 A081824 A199083 * A053011 A021133 A354238

Adjacent sequences: A109936 A109937 A109938 * A109940 A109941 A109942

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