Problems & Puzzles: Puzzles

Puzzle 218. Rupinski primes

Andrew Rupinski has been studying the numbers B(O, E, D), defined by the following conditions:

  1. B has D digits
  2. B has only two kind of digits: O (odd) and E (even)
  3. B is divided by 2^D


1)  B(3, 8, 23) 33333333333333383333888, because while conditions 1 & 2 are satisfied, 3 is not, that is to say 2^23 does not divide 33333333333333383333888.

2)  B(3, 8, 23) = 88888888888833383333888, because all the three conditions are satisfied. As a matter of fact 88888888888833383333888/2^23 = 10596381293396161

It's not hard demonstrate that B(O, E, D) is one singular number once O, E & D are given. "Singular" here means that there are always one, and no more than one, B number for a given triad O, E & D. Moreover, B can be easily constructed after O & E are given.

Suppose O, E & D are given then B(O, E, D) = 2^D*R is satisfied in a singular manner by a number B that is equal to the product of two singular numbers 2^D & a cofactor R.

Sometimes R is composite sometimes R is prime. Soon you'll learn that in order to R to be prime, we need that  O & E are coprimes.

Rupinski has been studying in particular these instances O, E, D where R is prime.

For example he has told me that R is prime for the following (O, E, D) triads: (3, 8, 23), (7, 6, 167), (9, 8, 167) and a few others.

I have found that R is a titanic prime for (7,  6, 1449) and for sure the smallest one.


1. Demonstrate that given (O, E & D), B is unique and show how to compute it.

2. Find the earliest Rupinski titanic prime for every pair (O, E)?


Ken Wilke, Jon Wharf and J. K, Andersen sent contributions to this puzzle:

Ken Wilke wrote:

I saw Puzzle 218 this morning and I have an answer for question 1.

Let B be a D digit number such that B==0(mod 2^D) and each digit of B is either Q or E where Q and E are given odd and even digits respectively. ( I have chosen to use Q instead of O to avoid confusion with zero.) Since there are two choices of possible digits (Q and E) for each digit of B there are 2^d possible numbers B which can be constructed. We shall show that only one such choice of B satisfies the requirement that B==0(mod 2^D)

Proof: Consider the following sequence of numbers defined by T(n+1) = 10^n*f+T(n)where T(n) consists only of digits Q and E and T(n)==0(mod 2^n) for all integers D >= n >=1 and f is a digit to be determined. Then T(n+1) == 10^n*f + T(n) == 0 (mod 2^(n+1)). Then since T(n)==0(mod 2^n), we must have 10^n*f == -T(n)(mod 2^(n+1)). Thus 5^n*f == f == (-T(n))/(2^n)(mod 2). Note that T(n) == 0(mod 2^n)) guarantees that (-T(n)/2^n) is an integer. Thus at each stage f is uniquely determined to be odd or even. If f is odd, we take f = Q so that T(n+1) = 10^n*Q+T(n). Similarly if f is even we can take f = E so that T(n+1) = T(n+1) = 10^n*E+T(n). Each time the process is repeated cuts in half the possible choices for a properly constructed choice of B. Since T(1) must be divisible by 2, it suffices to take T(1) = E in order to guarantee that the process works. After D repetitions of the process we are left with the uniquely constructed integer B which satisfies all three conditions imposed on B. QED.


Jon Wharf wrote:

The proof of uniqueness is by induction, which also gives the construction:

Using only odd digit o and even digit e, only one single-digit number is divisible by 2: e. Now assume that we have a unique solution for n digits. That is, there is only one number, k, between 10^(n-1) and 10^n composed only of digits o and e which has k == 0 mod 2^n. First note that 10^n == 2^n mod 2^(n+1). So, looking at the first digit, o.(10^n) == 2^n mod 2^(n+1) and e.(10^n) == 0 mod 2^(n+1). In order to complete the number we require a number m between 10^(n-1) and 10^n composed only of digits o and e which has m == (either 0 or 2^n) mod 2^(n+1). But in either case m == 0 mod 2^n so only m=k will work.

Now if k=0 mod 2^(n+1) then only e.(10^n) + k == 0 mod 2^(n+1) (for n+1 digits) If k = 2^n mod 2^(n+1) then only o.(10^n) + k == 0 mod 2^(n+1) (for n+1 digits). In either case there a solution and there is only one solution for n+1 digits.

So the construction method builds up the number, one digit at a time: if B(o,e,d)/2^d is even, the first digit of B(o,e,d+1) is e; if B(o,e,d)/2^d is odd, it's o.

The logic also works when the even number is zero but following the process through it is clear that the odd number is never used - all you get is a lengthening string of zeroes.


J. K. Andersen wrote:

Question 1

B(O,E,D) can be constructed by appending the digit O or E to the left of B(O,E,D-1). Just test which one works.

Let odd O and even E be given.

The uniqueness of B(O,E,D) can be proved by induction on D. Induction start, D=1: B(O,E,1) = E is easy to see. Induction step, D>1: Assume F=B(O,E,D-1) is unique. By definition, 2^(D-1) divides F. Then 2^D divides either F or F+2^(D-1). 2^D always divides 2*10^(D-1) and 10^(D-1)+2^(D-1), so 2^D divides E*10^(D-1) and O*10^(D-1)+2^(D-1). Let G be a solution to B(O,E,D), i.e. G contains only digits O and E, and 2^D divides G. Case 1: The first digit of G is E. The digit E contributes E*10^(D-1) to G and this is divisible by 2^D, so the number made of the rest D-1 digits must also be divisible by 2^D. The unique F either satisfies this or not, giving 1 or 0 solutions. Case 2: The first digit of G is O. The digit O contributes O*10^(D-1) to G and this is 2^(D-1) (mod 2^D), so the number made of the rest D-1 digits must also be 2^(D-1) (mod 2^D). Then it is divisible by 2^(D-1) and must be F=B(O,E,D-1). The unique F is either 2^(D-1) (mod 2^D) or not, giving 1 or 0 solutions. Case 1 & 2 combined: If Case 1 gives a solution then Case 2 does not, and vice versa. It has now been proved that there is a unique solution and the solution appends O or E to the left of B(O,E,D-1).

Question 2

If O and E are both divisible by 3 then 3 divides B(O,E,D), more precisely

B(O,E,D) = 3*B(O/3,E/3,D).

Define R(O,E,D) = B(O,E,D)/2^D. This has around 0.7*D digits. If O and E are both divisible by 3 then the only prime is R(3,6,1) = R(9,6,1) = 6/2^1 = 3. If we allow E=0 (zero) then B(O,zero,D)=zero which can also be written as D zeros to get the right digit count. For all other combinations of O and E, I would guess there are infinitely many primes, based on heuristics. The earliest Rupinski titanic probable primes for different (O,E) pairs are: R(1,2,1998), R(1,4,4912), R(1,6,33587), R(1,8,7162), R(3,2,3991), R(3,4,5157), R(3,8,15021), R(5,2,3029), R(5,4,???), R(5,6,2328), R(5,8,1954), R(7,2,1870), R(7,4,1988), R(7,6,1449), R(7,8,1677), R(9,2,4391), R(9,4,3977), R(9,8,1976).

These were found with a C program using the Miracl bigint library and PrimeForm/GW. All seven R(O,E,D) in the list with D<2000 have been proved prime with Marcel Martin's Primo.

R(5,4,D) is not a titanic prime for D<32000 but there are sub titanic primes.


Records   |  Conjectures  |  Problems  |  Puzzles