A393035 - OEIS

%I #24 Mar 11 2026 10:32:55

%S 0,1,2,4,6,13,16,18,19,30,40,46,67,95,102,216,219,307,580,613,726,865,

%T 3042,8041,8629,8791,8801,12833,17250,23055,58771,74295,117723,144535

%N Indices k such that P(k)^2 + P(k+1)^2 is prime, where P(n) is the Padovan sequence A134816(n+1).

%C This sequence represents the indices k of the Padovan numbers whose sum of adjacent squares results in a prime. The primality of terms up to a(15) (index 102) was verified deterministically using SymPy's "isprime". The primality of a(23) (index 3042), a 744 digit number, was rigorously verified using the APRCL algorithm in PARI/GP. Terms from a(24) onwards are strong probable primes.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Padovan_sequence">Padovan sequence</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely%E2%80%93Cohen%E2%80%93Lenstra_primality_test">APRCL primality test</a>

%e For k = 0: P(0) = 1, P(1) = 1. 1^2 + 1^2 = 2, which is prime. So a(1) = 0.

%e For k = 1: P(1) = 1, P(2) = 1. 1^2 + 1^2 = 2, which is prime. So a(2) = 1.

%e For k = 2: P(2) = 1, P(3) = 2. 1^2 + 2^2 = 5, which is prime. So a(3) = 2.

%e For k = 3: P(3) = 2, P(4) = 2. 2^2 + 2^2 = 8, which is not prime.

%e For k = 4: P(4) = 2, P(5) = 3. 2^2 + 3^2 = 13, which is prime. So a(4) = 4

%o (Python)

%o from sympy import isprime

%o def a134816(n):

%o     # Padovan sequence generator

%o     a, b, c = 1, 1, 1

%o     for _ in range(n):

%o         a, b, c = b, c, a + b

%o     return a

%o def generate_sequence(limit):

%o     indices = []

%o     for k in range(limit):

%o         candidate = a134816(k)**2 + a134816(k+1)**2

%o         if isprime(candidate):

%o             indices.append(k)

%o     return indices

%o # The first 29 terms are found by calling generate_sequence(17251)

%Y Cf. A000040, A134816.

%K nonn,hard,more

%O 1,3

%A _Fırat Karayıldız_, Feb 28 2026

%E a(30)-a(34) from _Michael S. Branicky_, Mar 01 2026