The Contest Center - Mathematical Puzzles

Puzzles involving prime numbers and prime factors

W	I	N
I		O
N	O	W

PRIMES and FACTORS
The Contest Center
59 DeGarmo Hills Road
Wappingers Falls, NY 12590

W	I	N
I		O
N	O	W

Like this site?
Please tell a friend

Please sign our
Guestbook

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.

* Big Palindrome (based on an idea from Naim Uygun)
Find the smallest integer AB=C where A and B are both pan-digital, that is, contain all of the 10 digits 0 to 9, and the product C is a 20-digit palindrome.

Solved by: Paul Cleary

* 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

** 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=2⁵ appears in this short portion of the sequence. The square 16 occurs at 61 67.
       Find larger squares imbedded in the sequence of concatenated primes, and spanning 2 or more primes. To be listed, you must find a larger square than the ones already found by other solvers.

Solved by: Andreas Abraham (10 digits), Carlos Rivera (18 digits), Frank Rubin (52 digits), Nick McGrath (53 digits), Jens Kruse Andersen (54 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 = 3³×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

### 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².

*** 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

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

* 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

* 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

* 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

* 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

* 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 n^th 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

* 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 n^th prime. Show that there are no primes such that D(p(n)) = n.

Solved by: Lee Morgenstern, Mark Rickert, P.M.A. Hakeem

### Prime Digital Sums #3
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 n^th 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.

** 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=2²×5, 21=3×7 and 22=2×11. The first 3 consecutive whole numbers each having 3 distinct prime factors are 644=2²×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

** 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

** 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

### 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 11₂=3 is prime and 11 is prime; 101₂=5 is prime and 101 is prime; 111₂=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

*** Kissing Primes #2
Find 6 primes which all kiss one another (that is, all 30 of their pairwise concatenations are also prime).

Solved by: Lee Morgenstern, Mark Rickert, Carlos Rivera, Hakan Summakoglu, Paul Cleary

*** 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).

*** Kissing Primes #4
Prove that there is a limit to the number, N, of primes you can have such that all of their N(N-1) pairwise concatenations are prime.

Solved by: Lee Morgenstern

### Kissing Primes #4
Determine the largest number, N, of primes you can have such that all of their N(N-1) pairwise concatenations are prime.

** 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

* 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

** Square and Prime (contributed by Sudipta Das)
Kenny has gone to a lecture by Jenny, a famous mathematician. He 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

* 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

** 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

### Prime Digits #2
Let D be any decimal digit. 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

*** 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

### 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

*** Between 2 and 3
       It is well known that there are an infinite number of primitive integer solutions to A²+B²=C² and that there are no non-trivial integer solutions to A³+B³=C³. Where is the boundary between the solvable and the unsolvable?
       It does not make much sense to talk about integer equations A^r+B^r=C^r 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.]

### 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.]

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 >>>