Primes of the form 4*10^n+1 and primes of the form 16*100^n+1
 

Here the problem:

With Pari/Gp I found that 4*10^n+1 is prime for the following values of n (serach limit n=4005$):

$0,1,2,3,13,229,242,309,957,1473,1494,3182,3727$

On the other hand, I found that, squaring 4 and 10, the number 16*100^n+1 is prime with the same search limit $n=4005$ for the following values of $n$:

$0,1,2,9,18,29,34,39,42,47,75,89,95,343,406,420,1154,1265,1442,3067,4002$

I would have expected more primes of the shape 4*10^n+1 than primes of the form 16*100^n+1, because of the growth-rate. Instead it is the contrary. Is there any mathematical reason for this phenomenon and do you think that in the long run, the lead switches?

(There is a typo in the title...16*100^n+1 is correct)

FWIW, [OEIS]056806[/OEIS] has more terms for the first sequence.

OK
 

Ok but why 16*100^n+1 seems to give more primes than 4*10^n+1?
With Pfgw we could go further in the investigation...maybe there is a reason due to the factors.

[QUOTE=enzocreti;515812]Ok but why 16*100^n+1 seems to give more primes than 4*10^n+1?
With Pfgw we could go further in the investigation...maybe there is a reason due to the factors.[/QUOTE]

I don't know. Perhaps random luck caused the second sequence to have lot of small primes. Perhaps there may be some differences due to the factors, as you suggested. I would suggest to try to search the second sequence a bit higher (say upto 30,000) and see if it continues to find more primes.

reason
 

the factors of 16*100^n+1 cannot be of the form 4k+3?

7785 another prp found
 

for 7785 pfgw found another prp!!!

explanation
 

in the case of numbers 16*100^n+1 should be many restrictions not present in the case 4*10^n+1 so far example they cannot be divisible by 7 or by primes 8k+1

[QUOTE=enzocreti;515816]the factors of 16*100^n+1 cannot be of the form 4k+3?[/QUOTE]
This is certainly part of the answer -- along with the fact that numbers 4*10^n + 1 [i]can[/i] have factors of this form (e.g. p = 7, 19, 23, 47, 59).

I don't know how relevant this is, but when n = 4k, 4*10^n + 1 has the Aurifeuillian (algebraic) factorization

4*10[sup]4k[/sup] + 1 = L*M =

(2*10[sup]2k[/sup] - 2*10[sup]k[/sup] + 1)*(2*10[sup]2k[/sup] + 2*10[sup]k[/sup] + 1).