Processing math: 100%

Thursday, November 7, 2019

Prepending and appending a repunit with the same number

Consider a repunit R(n) of n digits in decimal, i,e, the number consisting of n 1's which is equal to (10n1)/9. If we append and prepend R(n) with the same number k, which we will denote as  k|R(n)|k with | denoting concatenation of digits, will k|R(n)|k be prime? For instance, for k = 324 and n = 1111, k|R(n)|k=3241111324=22×112×281×23831. It turns out that if n is a power of 2, then k needs to have at least n digits for k|R(n)|k to be prime. In particular, we have the following result:

Theorem: If 2r is the largest power of 2 that divides n and k has at most 2r1 digits, then k|R(n)|k is not prime. This is true even if some of the digits of k are leading zeros.

Proof: If k has m digits, then k|R(n)|k=k(10n+m+1)+R(n)10m which is a multiple of gcd(R(n),10n+m+1).

Since 102r1=(102r11)×(102r1+1) and 9 does not divide 10n+1, by induction it is easy to show that 102w+1 is a divisor of  R(2r) for 1w<r. Since R(2r) is a divisor of R(2rs), 102w+1 is also a divisor of R(2rs).

For 1m<2r, let t be the 2-adic valuation (or 2-adic order) of m, i.e. t is the largest integer such that 2t divides m. This means that  0t<r.

Then 102rs+m+1=102tq+1=(102t)q+1 for some odd number q.

Since the sum of two odd powers aq+bq is divisible by a+b, this implies that 102rs+m+1 is divisible by 102t+1.

This implies that for n=2rs and for all 1m<2r, gcd(R(n),10n+m+1)102t+1>1, i.e. k|R(n)|k is not prime. QED

For example, for n = 32, the smallest k such that k|R(n)|k is prime is k = 10000000000000000000000000000077, a number with 32 digits. The smallest such k for different n's can be found in OEIS sequence A263182 (see also OEIS sequence A329121).

Wednesday, November 6, 2019

Product of a number and its reversal in decimal

The number 10119126106147652568 is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 5 ways. 

10119126106147652568 = 8848263411 * 1143628488 = 8044687521 * 1257864408 = 4884561702 * 2071654884 = 4440958722 * 2278590444 = 4082378742 * 2478732804.

Multiply this number by 10 and it is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 10 ways. 

101191261061476525680 = 88482634110 * 1143628488 = 80446875210 * 1257864408 = 48845617020 * 2071654884 = 44409587220 * 2278590444 = 40823787420 * 2478732804 = 24787328040 * 4082378742 = 22785904440 * 4440958722 = 20716548840 * 4884561702 = 12578644080 * 8044687521 = 11436284880 * 8848263411.

Friday, January 11, 2019

Numbers whose binary complement is larger than the binary complement of its square.

OEIS sequence A323192 lists numbers whose binary complement is larger than the binary complement of its square. The binary complement is defined as flipping each bit in its binary representation. For instance, 29 is 11101 in binary, so its binary complement is 2 which is 00010 in binary. Note that the binary complement function is not one-to-one, for instance the binary complement of 61 (111101 in binary) is also 2.  This function is not exactly the same as 1's complement in computer arithmetic, since the number of bits flipped is not fixed but is equal to the number of bits in the binary representation of the number.

Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form 2k1. It turns out this is true in general. In fact we can prove more. In particular, we can show that the terms of this sequence corresponds to numbers of the form 22k1 which are larger than 12+14+22k12k with k>0.

This result follows from the following theorem:

Theorem: if n is a term of OEIS sequence A323192, then n is of the form 22k1 for some k>0. In addition, 22k1 is a term if and only if it is larger than 12+14+22k12k.

Proof: suppose n has k bits in its binary representation, i.e. 2k1n<2k. Then n2 has either 2k1 or 2k bits.

First we show that if n is a term of the sequence, then n2 has 2k1 bits. Suppose n2 has 2k bits, i.e. n222k1. Then 22k1n2<2k1n. This is rearranged as n2n+2k22k>0. Solving this quadratic inequality leads to n>2k which contradicts the fact that n has k bits.

Thus n2<22k1 and 22k11n2<2k1n. Solving this inequality and combining it with n<22k1 shows that n must satisfy 22k1>n>12+14+22k12k.

To complete the proof, we need to show that for each k, there is at most one integer satisfying this inequality. This is easily verified for k=1. Assume that k>1. Let a=22k1 and b=12+14+22k12k.

Using the identity xy=(xy)/(x+y) it follows that ab=12+2k1422k1+14+22k12k<12+2k22k1+22k12k.

Since k2, 22k12k=22k1(121k)12 22k1. This implies that ab<12+2k2+1222k1=222+112<0.672. Thus it follows that there is at most one integer in the range between b and a.

The above discussion also completely characterizes the sequence. 22k1 is a term if and only if 22k122k1)<ab where ab is as defined above.

The criterion can be simplified as:
22k1 is a term if and only if it is larger than 12+14+22k12k. This concludes the proof.

Note that ab12 as k, i.e. for large k, the fractional part of 22k1 should be less than about 12 in order for the integer part to be a term.

The numbers k such that 22k1 is a term of OEIS sequence A323192 are listed in OEIS sequence A323062.

Monday, January 7, 2019

560106 and 601065

There is a remarkable property of the sequence of numbers 560106, 5606106, 56066106, 560666106, etc. Take any number of the sequence, say 56066106, reverse the digits: 60166560, multiply these 2 numbers, multiply the result by 10 and the result is a perfect square. Thus
56066106×60166065×10=33732769778928900=1836648302.

To see this, let us denote the decimal digits reversal of a number n as R(n).   Let a=56×104+k+106+6000×(10k1)/9 for k0. Then R(a)=601×103+k+65+6000×(10k1)/9. The number 10×a×R(a) can be written as 30360100×(10k+31)2/9 whose square root is 5510×(10k+31)/3.

It is clear the the digit reversals of these numbers, i.e. 601065, 6016065, 60166065, 601666065, ..., satisfy the same property.

Other numbers with this property can be found in OEIS sequence A323061.