All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Prime source (Posted on 2013-02-25) Difficulty: 5 of 5
Let us define an operation Op as follows: take a three-digit number N=100*a+10*b+c (a must be a non-zero digit) and evaluate
Op(N)= Na+Nb+Nc;
e.g. Op(203)= 2032+2030+2033=8406637;
Op(102)= 102+1+10404=10507.


The first example resulted in a prime number (8406637),
the second - a composite (10507=7*19*79).

A 3-digit number, which by means of Op(N) generates a prime we shall call a "prime source".

203 is a prime source.
101 is obviously the only three digit number that generates a prime source !

Now, the D5 problem: Find the largest prime source.

Reducing the degree of difficulty, we shall deal with three "limited editions":
D2: What is the smallest prime source?
D2: What is the largest prime source you can get?
D4: Find the largest prime source below 500.

Some facts and hints:
1. Testing all 3-digit numbers is counter-productive - either the b digit or the c digit (but not both) must be 0, otherwise N either divides Op(N)(no zero digits) or is even (b=c=0).
2. Op(501)>3.15*1013.
3. Op(990)>1.82*1027.
4. http://www.walter-fendt.de/m14e/primes.htm
links to a list of all primes below 1012.

Good luck.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 1 of 1

   10   for N=2 to 999
   20     A=N\100:B=(N\10)@10:C=N@10
   30     Op=N^A+N^B+N^C
   40     if fnPrime(Op) then print N,Op
   50   next
 9999   end
10000   fnOddfact(N)
10010   local K=0,P
10030   while N @ 2=0
10040     N=N\2
10050     K=K+1
10060   wend
10070   P=pack(N,K)
10080   return(P)
10090   '
10100   fnPrime(N)
10110   local I,X,J,Y,Q,K,T,Ans
10120   if N @ 2=0 then Ans=0:goto *EndPrime
10125   O=fnOddfact(N-1)
10130   Q=member(O,1)
10140   K=member(O,2)
10150   I=0
10160   repeat
10170     repeat
10180       X=fnLrand(N)
10190     until X>1
10200     J=0
10210     Y=modpow(X,Q,N)
10220     loop
10230       if or{and{J=0,Y=1},Y=N-1} then goto *ProbPrime
10240       if and{J>0,Y=1} then goto *NotPrime
10250       J=J+1
10260       if J=K then goto *NotPrime
10270       Y=(Y*Y) @ N
10280     endloop
10290    *ProbPrime
10300     I=I+1
10310   until I>50
10320   Ans=1
10330   goto *EndPrime
10340   *NotPrime
10350   Ans=0
10360   *EndPrime
10370   return(Ans)
10380   '
10400   fnLrand(N)
10410   local R
10415   N=int(N)
10420   R=(int(rnd*10^(alen(N)+2))) @ N
10430   return(R)
10440   '
10500   fnNxprime(X)
10510   if X @ 2=0 then X=X+1
10520   while fnPrime(X)=0
10530     X=X+2
10540   wend
10550   return(X)
10560   '

This program uses a probabilistic primality test and produces the following list, which starts with some numbers that have fewere than three digits (equivalent to leading zeros, which should be understood to be present, so as to supply the exponents for the three terms):

 3       29
 11      23
 12      157
 14      38431
 21      463
 23      12697
 38      4347792193369
 65      76579181251
 66      165307900033
 89      354292992513187291
 92      472161363286565137

Legitimate 3-digit N begin here, showing all the Prime Sources per the strict definition:

 203     8406637
 230     12219901
 308     80985213602898040129
 309     25681850577311050630819
 330     71874001
 350     5252230375001
 503     32198944966271
 603     48073293297531757
 650     75534919687500001
 960     692533996607238045696000001
 
The Factoris factoring utility  certifies all the results as being prime so the probabilistic nature of the prime test used by the program did not result in any spurious values, as any declaration of compositeness is strict, rather than probabilistic.


  Posted by Charlie on 2013-02-25 20:13:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information