Puzzles involving prime numbers and prime factors
W I N
I   O
N O W

The Contest Center
59 DeGarmo Hills Road
Wappingers Falls, NY 12590
W I N
I   O
N O W


A prime is an integer greater than 1 that cannot be evenly divided by another positive integer other than itself or 1. For example, 2, 3, 5, 7 and 11 are prime, but 9 is not a prime since it can be evenly divided by 3. The only even prime is 2.


We will post the names of anyone who solves these puzzles.
The puzzles are ranked according to difficulty.
* indicates an easy to moderate puzzle.
** indicates a tough puzzle.
*** indicates a puzzle for expert solvers.
### indicates the answer is not known.


* N+1 to N+5
       Find the smallest integer N such that N+1 is a prime, N+2 is the product of 2 primes, N+3 is the product of 3 primes, N+4 is the product of 4 primes and N+5 is the product of 5 primes.
Solved by:   Ender Aktulga, Naim Uygun, Kaustuv Sengupta


* Most Small Factors (contributed by Paul Cleary)
       Find the 10-digit number which has the most distinct factors <= 100.
Solved by:   P.M.A. Hakeem, Arthur Vause, Mark Rickert, Naim Uygun, Ender Aktulga


** Prime Squares (contributed by Carlos Rivera)
       Imagine that all of the primes are concatenated to form an infinite sequence of decimal digits
       2 3 5 7 11 13 17 19 23 29 31 37 ...
Within this sequence of digits there will be squares, cubes, and other numbers of interest. For example, 32=25 appears in this short portion of the sequence at 23 29. The square 16 occurs at 61 67.
       Find larger squares imbedded in the sequence of concatenated primes, and spanning 2 or more primes. [UPDATE] You no longer need to find a larger square to get listed. Anyone submitting a square of at least 60 digits will be listed.

Solved by:   Andreas Abraham (10 digits), Carlos Rivera (18 digits), Frank Rubin (52 digits), Nick McGrath (53 digits), Jens Kruse Andersen (54 digits), Arthur Vause (55, 100, 1000 digits), Paul Cleary (70 digits, 100 digits), Frank Rubin (200, 400, 600, 800, 1000 digits), Paul Cleary (1100 digits), Frank Rubin (1200, 1400, 1600 digits), Paul Cleary (1400, 1600, 4000 digits), Arthur Vause (2000 digits)


* Abundant Numbers
       A whole number N is called abundant if the sum of its divisors is more than 2N. For example, 12 is the first abundant number. The sum of its divisors 1, 2, 3, 4, 6, 12 is 28, which is more than 2×12. The smallest abundant number that is not divisible by 2 is 945 = 33×5×7. What is the smallest abundant number which not divisible by 2 or 3?

Solved by:   Patrick Capelle, Shyam Sunder Gupta, Mark Rickert, P.M.A. Hakeem, Claudio Meller, Paul Cleary, Hakan Summakoglu, Naim Uygun, Ionut-Zaharia Chirila, Ender Aktulga, Kaustuv Sengupta


** Prime Sequence
       Consider the sequence of primes 2, 5, 11, 23, 47 formed using the rule pn+1=2pn+1. Find longer sequences, perhaps using different starting primes or different constants, say pn+1=apn+b.

Solved by:   P.M.A. Hakeem (15 solutions, from 6 to 9 primes), Paul Cleary (89 solutions, from 8 to 13 primes), Ionut-Zaharia Chirila (8 primes), Naim Uygun (15 solutions, from 7 to 10 primes), Ender Aktulga (56 solutions, 8 to 9, one 11), Ahmet Saracoglu (590 solutions, from 8 to 11 primes), Arthur Vause (54 solutions, from 17 to 19 primes)


### Prime Lattices
       Let s1,s2,...,sm and t1,t2,...,tn be strings of decimal digits, all of equal length. Then a prime lattice of order m,n is a set of primes 
   s1t1  s1t2  ...  s1tn
   s2t1  s2t2  ...  s2tn
      ...          ...
   smt1  smt2  ...  smtn
For example 
   11  17
   31  37
and 
   1009  1051
   1109  1151
are prime lattices of order 2,2 and 
   1009  1051  1087
   1109  1151  1187
   1409  1451  1487
   4909  4951  4987
is a prime lattice of order 4,3.

       Prove that there are prime lattices of every order.


### Sum of Squares
       Which whole numbers are equal to the sum of the squares of their prime divisors? For example, 16=2×2×2×2=2²+2²+2²+2² and 27=3×3×3=3²+3²+3².

Progress:   Giorgos Kalogeropoulos has found 123-digit, 163-digit and 179-digit examples.


*** Prime Order
       Prove that for every N>1 the integers from 1 to N can be arranged in an order such that the sum of any two consecutive numbers is a prime. For example,
9, 8, 3, 4, 1, 2, 5, 6, 7, 10

Solved by:   P.M.A. Hakeem, Ionut-Zaharia Chirila


Cyclic Permutations
       What is the largest prime such that every cyclic permutation of its decimal digits is also prime? For example, 197, 971 and 719 are all prime. [Your prime must have at least 2 distinct digits.]

Solved by:   Nick McGrath, Andreas Abraham, Denis Borris, Mark Rickert, Hakan Summakoglu, Paul Cleary, P.M.A. Hakeem, Naim Uygun, Ionut-Zaharia Chirila, Ender Aktulga


* Web Counter
       A certain website has a counter which records the number of hits each day, and keeps a running total. The site gets between 10 and 20 hits, inclusive, per day. The webmaster noticed that the running total was always prime. What is the largest number of days the site could be up? What is the largest number of days if the counter did not start from 1?

Solved by:   Nick McGrath, P.M.A. Hakeem, Paul Cleary, Ender Aktulga


* Powers of P (contributed by Nick McGrath)
       If P and P^2+8 are both primes, prove that P^3+16 is also prime.

Solved by:   Ritwik Chaudhuri, Carlos Rivera, Alex Liu, Le My An, Rakesh Banka, Purushottam Dixit, Jens Kruse Andersen, Brian Nist and Patrick Pase, P.M.A. Hakeem, Mark Rickert, Hakan Summakoglu, Arthur Vause, Paul Cleary, Naim Uygun, Ionut-Zaharia Chirila, Kushal Khaitan, Ender Aktulga, Kaustuv Sengupta


* Sum of Two
       Find 3 integers such that the sum of any 2 of them is a prime.
       Find an expression that generates all solutions.

Solved by:   Carlos Rivera, Colin Bown, Nick McGrath, Andreas Abraham, Mark Rickert, P.M.A. Hakeem, Hakan Summakoglu, Arthur Vause, Ionut-Zaharia Chirila, Ender Aktulga


* Sum of Three
       What is the largest number of positive integers you can have such that the sum of any 3 of them is a prime? An integer may be used twice, but not more than twice.

Solved by:   Steve Spindler, Carlos Rivera, Mark Rickert, P.M.A. Hakeem, Hakan Summakoglu, Ionut-Zaharia Chirila, Kaustuv Sengupta


* Prime Digital Sums #1
       The digital sum D(n) of an integer n is the sum of its decimal digits. For example, D(123)=6. Let p(n) denote the nth prime. Show that there are no primes such that p(n) = D(n).

Solved by:   Lee Morgenstern, Andreas Abraham, Mark Rickert, P.M.A. Hakeem, Ritwik Chaudhuri, Arthur Vause, Ionut-Zaharia Chirila, Ender Aktulga


* Prime Digital Sums #2
       The digital sum D(n) of an integer n is the sum of its decimal digits. For example, D(123)=6. Let p(n) denote the nth prime. Show that there are no primes such that D(p(n)) = n.

Solved by:   Lee Morgenstern, Mark Rickert, P.M.A. Hakeem, Ionut-Zaharia Chirila


### Prime Digital Sums #3
       The digital sum D(n) of an integer n is the sum of its decimal digits. For example, D(123)=1+2+3=6. Let p(n) denote the nth prime. Show that there are infinitely many primes such that D(p(n)) = D(n).
This problem was first proposed by G. L. Honaker Jr. in 1987.


** 5 Factors
       The first 2 consecutive whole numbers each having 2 distinct prime factors are 14=2×7 and 15=3×5. The first 2 consecutive whole numbers each having 3 distinct prime factors are 230=2×5×23 and 231=3×7×11. The first 3 consecutive whole numbers each having 2 distinct prime factors are 20=22×5, 21=3×7 and 22=2×11. The first 3 consecutive whole numbers each having 3 distinct prime factors are 644=22×7×23, 645=3×5×43 and 646=2×17×19.
       Find the first 3 consecutive whole numbers each having 5 distinct prime factors.

Solved by:   Sudipta Das, Nick McGrath, Jean-Charles Meyrignac, Andreas Abraham, Denis Borris, Jens Kruse Andersen, Shyam Sunder Gupta, Mark Rickert, P.M.A. Hakeem, Claudio Meller, Paul Cleary, Hakan Summakoglu, Arthur Vause, Naim Uygun, Frederick Schneider, Ionut-Zaharia Chirila, Ender Aktulga, Kaustuv Sengupta, Turgay Yüktaş


** Factors #2
       Find the smallest whole number N such that N+1 has 1 prime factor, N+2 has 2 prime factors, ..., N+k has k prime factors. For distinct prime factors the solution for k=3 is N=63, since 64 has factor 2, 65 has factors 5 and 13, and 66 has factors 2, 3, and 11. For total prime factors the solution for k=3 is N=60, since 61 has factor 61, 62 has factors 2 and 31, and 63 has factors 3, 3, and 7.
       Solve for k=4 through 6 for distinct prime factors, and k=4 through 7 for total prime factors.

Solved by:   Nick McGrath, Jens Kruse Andersen, Shyam Sunder Gupta, Paul Cleary, Hakan Summakoglu, Ender Aktulga


** Twice Prime (jointly with Sudipta Das)
       (A) Prove that a triangle with integer sides cannot have an area that is prime. (B) Find a triangle with rational sides whose area and perimeter are both prime.

Solved by:   Jean Jacquelin, Mark Rickert, Arthur Vause, P.M.A. Hakeem, Ender Aktulga


### Binary and Decimal
       Do there exist an infinite number of binary numbers which are prime, such that when their digits are interpreted as decimal numbers they are also prime? For example 112=3 is prime and 11 is prime; 1012=5 is prime and 101 is prime; 1112=7 is prime but 111=3×37 is composite.


** Kissing Primes #1
       We will say two primes kiss if both of their concatenations are also prime. For example, 3, 37 and 67 all kiss since all of the concatenations 337, 373, 367, 673, 3767 and 6737 are prime. Find 5 primes such each one kisses all of the others.

Solved by:   Carlos Rivera, Lee Morgenstern, Andreas Abraham, Mark Rickert, P.M.A. Hakeem, Paul Cleary, Hakan Summakoglu, Ahmet Saracoglu, Naim Uygun, Ionut-Zaharia Chirila, Ender Aktulga


*** Kissing Primes #2
       Find 6 primes which all kiss one another (that is, all 30 of their pairwise concatenations are also prime).
       Extra credit: Find a solution where all of the primes have the same number of digits.

Solved by:   Lee Morgenstern, Mark Rickert, Carlos Rivera, Hakan Summakoglu, Paul Cleary, P.M.A. Hakeem, Ahmet Saracoglu, Ender Aktulga
Extra credit: Lee Morgenstern (2 solutions), Mark Rickert (8 solutions)


*** Kissing Primes #3
       Find 7 primes such that the most pairs kiss (that is, as many as possible of their 42 pairwise concatenations are also prime).

Solved by:   Lee Morgenstern (13 solutions)


** 3 Primes
       Find 3 primes such that all of their 12 possible concatenations are also prime. For example, given the primes 3, 7 and 13, the concatenations are 37, 73, 313, 133, 713, 137, 3713, 3137, 7313, 7133, 1337 and 1373, of which 6 are prime and 6 are composite.

Solved by:   Carlos Rivera, Mark Rickert, Hakan Summakoglu, Paul Cleary, P.M.A. Hakeem, Ender Aktulga


* Up to 35 (contributed by Ritwik Chaudhuri)
       Suppose that S is a set of N distinct positive integers, and that no member of S has a prime factor greater than 35. Let P be the set of products of members of S taken 2 at a time. (For example, if x, y and z are members of S, then xy, xz and yz will be members of P.)
       What is the smallest value of N for which it is certain that P contains a square?

Solved by:   Nick McGrath, Gaurav Agrawal, Mark Rickert, Arijit Bhattacharyya, P.M.A. Hakeem, Claudio Baiocchi, Kaustuv Sengupta


** Square and Prime (contributed by Sudipta Das)
       Kenny has gone to a lecture by Jenny, a famous mathematician. Kenny tells Lenny that Jenny handed everyone at the lecture 2 cards, one containing a 5-digit prime, and the other containing a 5-digit square. All of the cards held different numbers. Then she asked everyone to add their 2 numbers, and amazingly they all got the same sum. Kenny says it's lucky that Lenny didn't attend, because then the trick would have been impossible.
       What was the sum they all got?

Solved by:   Carlos Rivera, Andreas Abraham, Nick McGrath, Jens Kruse Andersen, Mark Rickert, P.M.A. Hakeem, Paul Cleary, Hakan Summakoglu, Jeffrey Heleen, Naim Uygun, Ender Aktulga, Kaustuv Sengupta, Ionut-Zaharia Chirila


* Differences (contributed by Sudipta Das)
       What is the largest number of distinct positive integers you can have such that the difference between any two of them is prime, and this difference divides both of those numbers?

Solved by:   Carlos Rivera, Nick McGrath, Ritwik Chaudhuri, Arijit Bhattacharyya, Mark Rickert, P.M.A. Hakeem, Hakan Summakoglu, Arthur Vause, Ender Aktulga, Ionut-Zaharia Chirila


** Differences #2
       What is the largest number of distinct positive integers you can have such that most of their pairwise differences are prime? For example, among (2, 4, 6, 11, 13, 15) there are 15 pairwise differences, of which 10 are prime.

Solved by:   P.M.A. Hakeem


** Prime Digits
       Find a prime number where replacing all occurrences of one of the decimal digits it contains by any other digit produces another prime. For example, suppose we chose the digit 6 in the prime 1663. Then the 9 integers 1003, 1113, 1223, etc. would all need to be prime.

Solved by:   Carlos Rivera, Hakan Summakoglu, Paul Cleary, Arthur Vause, Ender Aktulga, Naim Uygun


### Prime Digits #2
       For each decimal digit D, find the largest integer such that replacing each of its distinct decimal digits by D produces a prime. For example, if D is 3 and the chosen integer were 572251, then all of the integers 572253, 573351, 372231 and 532251 would need to be prime.


* Prime Density #1 (based on a submission from Sudipta Das)
       Let P be a prime of D digits, and consider the substrings of the digits of P with lengths greater than 1 and less than D.  For example, if P is 1373, then the substrings are 13, 137, 37, 373 and 73.  In this case they are all prime.  Let the substring length SL(P) be the combined length of all substrings of P, and the prime substring length PSL(P) be the combined length of all substrings which are prime (with leading zeros allowed).  Then let the prime substring density PSD(P) be PSL(P)/SL(P).  So SL(1373)=PSL(1373)=12 and PSD(1373)=1.
       (A) Find the largest prime P for which PSD(P) is 1. (B) Find the 10-digit prime P for which PSD(P) is greatest.

Solved by:   Sudipta Das, Paul Cleary, P.M.A. Hakeem, Ender Aktulga


*** Prime Density #2
       Let the prime substring density be defined as above.  Find the largest prime P for which PSD(P) > 1/2, or show that there are an infinite number of such primes.


* Prime Density #3
       Let N be an integer of D digits, and consider all substrings of the digits of N with lengths from 1 to D, inclusive, but disallowing strings with leading zeroes.  For example, if N is 10305, then the substrings are 1, 10, 103, 1030, 10305, 3, 30, 305, and 5.  Let the substring length SL(N) be the combined length of all such substrings of N, and the prime substring length PSL(N) be the combined length of all such substrings which are prime.  Then let the prime substring density PSD(N) be PSL(N)/SL(N).  So SL(10305)=22, PSL(10305)=5 and PSD(10305)=5/22, or about 0.227.
       Using this new definition, (A) find the largest integer whose prime substring density is 1, and (B) find the 10-digit integer whose prime substring density is greatest.

Solved by:   P.M.A. Hakeem, Ender Aktulga


### Prime Density #4
       Let the prime substring density be defined as above.  Find the largest integer N for which PSD(N) > 1/2, or show that there are an infinite number of such integers.


*** Twin Prime Magic Square (contributed by Sudipta Das)
       Twin primes are primes whose difference is 2, such as 5 and 7. Using only the smaller numbers in sets of twin primes, form a 3x3 Magic Square (a 3x3 array of numbers where all of the rows and columns, and both of the main diagonals have the same sum). Find the Magic Square whose sum is smallest using only 9-digit twin primes.

Solved by:   Carlos Rivera, Mark Rickert, Arthur Vause


*** Between 2 and 3
       It is well known that there are an infinite number of primitive integer solutions to A2+B2=C2 and that there are no non-trivial integer solutions to A3+B3=C3. Where is the boundary between the solvable and the unsolvable?
       It does not make much sense to talk about integer equations Ar+Br=Cr where r is an arbitrary real number, so we approach the problem in a more abstract way. The radical of an integer N, denoted rad(N), is defined as the product of the distinct prime factors of N. Thus, for example, rad(6)=rad(12)=rad(18)=rad(36)=6. Define the power of N, denoted power(N), as log(N)/log(rad(n)). For example, power(32)=5.
       Define the power of a triple A+B=C, denoted power(A,B,C), where gcd(A,B,C)=1 to be min(power(A),power(B),power(C)). Here are two examples:
power (61^4, 3^13*53, 2^13*5*7^4) = 3.6008
power (5^9*23, 2^6*3^5*17^3, 7^2*19^5) = 3.7135

       Find one or more triples of higher power. [Extra credit: Find a triple of power 4 or greater.] [Extra-extra credit: Determine the upper limit, or prove that none exists.]

Solved by:   Frederick Schneider, Arthur Vause


### Rubin Prime Conjecture
       Prove that for every integer n>1 there is at least one prime between n and n+(ln n)². [Jean Jacquelin has informed me that this conjecture is very similar to a conjecture made by Daniel Shanks in 1964.]


** Rubin Prime Function (based on a suggestion from Naim Uygun)
       The Rubin prime function R(N) is defined as the smallest integer S such that there are at least N primes between S and S+(ln S)², inclusive. Evaluate R(N) for all values of N up to ... however high you can.
       Extra credit: Find an expression that accurately approximates R(N).

Solved by:   Naim Uygun (N=41), Ender Aktulga (N=41), Paul Cleary (N=48), Arthur Vause (N=45)

Extra credit:   Frank Rubin

Send email        Send us an email to submit answers to these problems, to ask for help, or to submit new problems. We welcome new puzzles from our visitors.
      
Be sure to change the $ to an @ in our email address.


Quick Links
Interactive Online Games
<<< PREV HOME MAP NEXT >>>


© Copyright 2024 The Contest Center