Consider a repunit R(n) of n digits in decimal, i,e, the number consisting of n 1's which is equal to (10n−1)/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 2r−1 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 102r−1=(102r−1−1)×(102r−1+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 1≤w<r. Since R(2r) is a divisor of R(2rs), 102w+1 is also a divisor of R(2rs).
For 1≤m<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 0≤t<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 1≤m<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).
Thursday, November 7, 2019
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.
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 ⌊√2k−1⌋. 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 ⌊√22k−1⌋ which are larger than 12+√14+22k−1−2k 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 ⌊√22k−1⌋ for some k>0. In addition, ⌊√22k−1⌋ is a term if and only if it is larger than 12+√14+22k−1−2k.
Proof: suppose n has k bits in its binary representation, i.e. 2k−1≤n<2k. Then n2 has either 2k−1 or 2k bits.
First we show that if n is a term of the sequence, then n2 has 2k−1 bits. Suppose n2 has 2k bits, i.e. n2≥22k−1. Then 22k−1−n2<2k−1−n. This is rearranged as n2−n+2k−22k>0. Solving this quadratic inequality leads to n>2k which contradicts the fact that n has k bits.
Thus n2<22k−1 and 22k−1−1−n2<2k−1−n. Solving this inequality and combining it with n<√22k−1 shows that n must satisfy √22k−1>n>12+√14+22k−1−2k.
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=√22k−1 and b=12+√14+22k−1−2k.
Using the identity √x−√y=(x−y)/(√x+√y) it follows that a−b=−12+2k−14√22k−1+√14+22k−1−2k<−12+2k√22k−1+√22k−1−2k.
Since k≥2, √22k−1−2k=√22k−1(1−21−k)≥√12 √22k−1. This implies that a−b<−12+2k√2+1√2√22k−1=2√2√2+1−12<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. ⌊√22k−1⌋ is a term if and only if √22k−1−⌊√22k−1)⌋<a−b where a−b is as defined above.
The criterion can be simplified as:
⌊√22k−1⌋ is a term if and only if it is larger than 12+√14+22k−1−2k. This concludes the proof.◼
Note that a−b→12 as k→∞, i.e. for large k, the fractional part of √22k−1 should be less than about 12 in order for the integer part to be a term.
The numbers k such that ⌊√22k−1⌋ is a term of OEIS sequence A323192 are listed in OEIS sequence A323062.
Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form ⌊√2k−1⌋. 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 ⌊√22k−1⌋ which are larger than 12+√14+22k−1−2k 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 ⌊√22k−1⌋ for some k>0. In addition, ⌊√22k−1⌋ is a term if and only if it is larger than 12+√14+22k−1−2k.
Proof: suppose n has k bits in its binary representation, i.e. 2k−1≤n<2k. Then n2 has either 2k−1 or 2k bits.
First we show that if n is a term of the sequence, then n2 has 2k−1 bits. Suppose n2 has 2k bits, i.e. n2≥22k−1. Then 22k−1−n2<2k−1−n. This is rearranged as n2−n+2k−22k>0. Solving this quadratic inequality leads to n>2k which contradicts the fact that n has k bits.
Thus n2<22k−1 and 22k−1−1−n2<2k−1−n. Solving this inequality and combining it with n<√22k−1 shows that n must satisfy √22k−1>n>12+√14+22k−1−2k.
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=√22k−1 and b=12+√14+22k−1−2k.
Using the identity √x−√y=(x−y)/(√x+√y) it follows that a−b=−12+2k−14√22k−1+√14+22k−1−2k<−12+2k√22k−1+√22k−1−2k.
Since k≥2, √22k−1−2k=√22k−1(1−21−k)≥√12 √22k−1. This implies that a−b<−12+2k√2+1√2√22k−1=2√2√2+1−12<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. ⌊√22k−1⌋ is a term if and only if √22k−1−⌊√22k−1)⌋<a−b where a−b is as defined above.
The criterion can be simplified as:
⌊√22k−1⌋ is a term if and only if it is larger than 12+√14+22k−1−2k. This concludes the proof.◼
Note that a−b→12 as k→∞, i.e. for large k, the fractional part of √22k−1 should be less than about 12 in order for the integer part to be a term.
The numbers k such that ⌊√22k−1⌋ 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×(10k−1)/9 for k≥0. Then R(a)=601×103+k+65+6000×(10k−1)/9. The number 10×a×R(a) can be written as 30360100×(10k+3−1)2/9 whose square root is 5510×(10k+3−1)/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.
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×(10k−1)/9 for k≥0. Then R(a)=601×103+k+65+6000×(10k−1)/9. The number 10×a×R(a) can be written as 30360100×(10k+3−1)2/9 whose square root is 5510×(10k+3−1)/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.
Subscribe to:
Posts (Atom)