Problems & Puzzles:
Andrew Rupinski has been
studying the numbers B(O, E, D), defined by the following conditions:
- B has D digits
- B has only two kind of digits: O
(odd) and E (even)
- B is divided by 2^D
1) B(3, 8, 23)
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:
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).
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),
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.