Prime 479

[enzocreti]

Originally Posted by CRGreathouse

I suspect not. 10^25, probably. 10^35, only with great effort unless there are more features than meet the eye. But not 10^50.

Which could be the heuristic for this type of primes?
They must have a lot of restrictions true?

They must start with digit 4, end with digit 7 or 9...
so it is very hard to find another, isnt?

[enzocreti]

Originally Posted by Dr Sardonicus

I wonder what a little elementary number theory might reveal...

The most significant digit (MSD) d of p_k would have to be even, so d = 2, 4, 6, or 8. Since d < 9, we can say that the MSD of p_k+1 is either d or d+1. If d > 4, 2*p_k+1 would have more digits than p_k, so the only possibilities are d = 2 or d = 4.

If 2*p_k+1 == 2 (mod 10), then p_k+1 == 1 (mod 5). If 2*p_k+1 == 4 (mod 10), then p_k+1 == 2 (mod 5).

So, either p_k has MSD d = 2, and p_k+1 == 1 (mod 10), or p_k has MSD d = 4, and p_k+1 == 7 (mod 10).

These conditions (especially the MSD being either 2 or 4) narrow things down a bit...

Do you think that another prime of this type could appear with a good chance below 10^20?

[enzocreti]

Originally Posted by enzocreti

Do you think that another prime of this type could appear with a good chance below 10^20?

479 is also 1 mod 239
so
479 divides every number of the form 2^(239*k)-1

[CRGreathouse]

I wrote unlovely code for checking, maybe someone can improve on my method, but I thought the idea was worth posting. The first function can verify that there are no other solutions up to 10^10 in a minute or none up to 10^12 in an hour. The final function verifies that there are none with 13 digits and it takes less than a second. It should take about 10-12 times as long for each 2 additional digits (though it is hard-coded to check 13 digits, you'll need light tinkering to make it work for other numbers of digits; note that even and odd numbers of digits are slightly different).

If someone cares about this problem, they can use this to get a decent start on it. It should easily get you up to 22 digits in a few hours, less if you compile (mark everything in slight :small). 24 digits should be achievable in a day.

checksmall(maxdigits,mindigits=3)=
{
	if(maxdigits>18,error());
	my(D=10^(mindigits-3));
	for(d=mindigits,maxdigits,
		D*=10;
		forstep(initial=45*D,49*D,2*D,
			forprimestep(p=initial+9,initial+D-1,10,
				my(q=fromdigits(Vecrev(digits(p)))/2);
				if(q>p && q-p <= 1442 /*&& q%10==7*/ && isprime(q) && q==nextprime(p+1),
					print(p" "q)
				)
			)
		)
	);
}
customdigits(n, baseArray, mx=oo)=
{
	my(v=vector(#baseArray));
	forstep(i=#baseArray,1,-1,
		my(b=baseArray[i], d=divrem(n,b));
		if(d[1]>mx, return(0));	\\ failed -- some digit was larger than mx
		v[i]=d[1];
		n=d[2];
	);
	if(n==0,
		Vec(v)
	,
		0	\\ failed -- nonzero remainder
	);
}
check13()=
{
	\\ 10^7-10^5, 10^8-10^4, etc. Do the algebra here, these solve for the digits not given explicitly in the loop.
	\\ Worth checking: can you get one more digit here, i.e., get rid of the for(f= loop by adding another entry to the vector?
	my(bigdigits=[9800000, 99980000, 999998000, 9999999800, 99999999980]);
	forstep(a=5,9,2,
		my(Na=(40+a)*10^11+9,Ra=9*10^12+10*a+4,million=10^6);
		for(b=0,9,
			my(Nb=Na+10^10*b,Rb=Ra+100*b);
			for(c=0,9,
				my(Nc=Nb+10^9*c,Rc=Rb+1000*c);
				for(d=0,9,
					my(Nd=Nc+10^8*d,Rd=Rc+10^4*d);
					for(e=0,9,
						my(Ne=Nd+10^7*e,Re=Rd+10^5*e);
						for(f=0,9,
							my(mf=million*f,N=Ne+mf,R=Re+mf,target=2*N-R,cd);
							if(target>999988000020 || target<0 || target%10, next);	\\ all 9s
							cd=customdigits(target/10,bigdigits,9);
							if(cd!==0,
								my(sol=concat(concat([4,a,b,c,d,e,f],cd),9));
								print(sol);
							)
						)
					)
				)
			)
		)
	);
}

[CRGreathouse]

FYI: I don't have a general proof that the sums of 0..9 x bigdigits are unique in general; I just verified this particular case directly. More thought would be needed for larger cases where brute force isn't viable. I hope this is not a barrier.

Originally Posted by enzocreti

Do you think that another prime of this type could appear with a good chance below 10^20?

Heuristics are hard, just do the calculation.

To construct one, find out how often 2*N-R is in the right region (in this case, 0..999988000020, where the constant is 9 times the sum of the values in bigdigits), then figure out how often customdigits would succeed in that region -- probably about 1/baseArray[1] -- then divide by the log of 47... (with the appropriate number of digits), squared. Now find some constant to take into account all the digits you've fixed and how they affect primality (multiply by 2/1 * 5/4 since your initial number isn't divisible by 2 or 5, probably the same again for the second, and something for the 3s... hmm... multiply by 3/2, I think, since if one is divisible by 3 so is the other). Maybe some infinite product too, I'm not sure, but in any case you can approximate it by 1 if you can't be bothered.

That gives you the expected number for one digit length. Now do an infinite sum (might be best to split apart even/odd).

So... yecch. Feel free to work through that if you like.

[CRGreathouse]

Originally Posted by CRGreathouse

FYI: I don't have a general proof that the sums of 0..9 x bigdigits are unique in general; I just verified this particular case directly. More thought would be needed for larger cases where brute force isn't viable. I hope this is not a barrier.

It's not, the quotients are greater than 10 so the sums are forced to be unique.

[LaurV]

Ok, so, in abstract: take two consecutive primes, invert one of them, if the inverted one is a multiple of the other (obviously the other is prime, so the reverse can't be true) then write the prime, the reverted, and the multiple. Repeat by reverting the other prime (so we have both the (n, n+1) and (n, n-1), just for checking how it goes). With few tricks this can be done very fast, and it is kind of interesting that to some reasonable search limits, the only solutions are:

         23,          92, 4
        233,         932, 4
        487,         974, 2
       2333,        9332, 4
      23333,       93332, 4
12966666703, 90766666921, 7
etc.

of course, all primes of the form 23..33 will give a "4" solution if 23..39 is also prime (YES, the pair is in reverse order than the initial puzzle posted, and NO, 23...35 and 23...37 can't be prime!), but except of them, it seems to be none other. However, the "feeling" says the number of solutions must be infinite here...
Edit: This may spark another puzzle: search for prime pairs (23..3, 23..3+6) hehe...
Edit 2: the same number of 3's ! Of course, we know that all this numerology has no theoretical importance. But it looks like nothing to do Saturday afternoon...
Edit 3: (after 2 hours in which the real life bothered me - it is good to be supermod and not have the 1 hour edit restriction, and as long as nobody posted after me, I do not consider this a power abuse )

gp > for(i=1,2500,if(isprime(z=((7*10^i-1)/3))&&isprime(z+6),print(i"        ")); printf("...%d...%c",i,13))
1
2
3
4
94

so

gp > print((7*10^94-1)/3)
23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

is also a solution