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 $(10^n-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 = 2^2\times 11^2 \times 281\times 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 $2^r$ is the largest power of 2 that divides n and k has at most $2^r-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(10^{n+m}+1) + R(n)10^m$ which is a multiple of gcd$(R(n),10^{n+m}+1)$.

Since $10^{2^r} - 1 = (10^{2^{r-1} -1})\times (10^{2^{r-1} + 1})$ and 9 does not divide $10^n+1$, by induction it is easy to show that $10^{2^w} + 1$ is a divisor of  $R(2^r)$ for $1 \leq w < r$. Since $R(2^r)$ is a divisor of $R(2^r s)$, $10^{2^w} + 1$ is also a divisor of $R(2^r s)$.

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

Then $10^{2^r s+m}+1 = 10^{2^t q}+1 = (10^{2^t})^q + 1$ for some odd number $q$.

Since the sum of two odd powers $a^q+b^q$ is divisible by $a+b$, this implies that $10^{2^r s+m}+1$ is divisible by $10^{2^t}+1$.

This implies that for $n = 2^r s$ and for all $1 \leq m < 2^r$, gcd$(R(n),10^{n+m}+1) \geq 10^{2^t}+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 $\lfloor\sqrt{2^k-1}\rfloor$. 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 $\lfloor\sqrt{2^{2k-1}}\rfloor$ which are larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$ 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 $\lfloor\sqrt{2^{2k-1}}\rfloor$ for some $k > 0$. In addition, $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.

Proof: suppose $n$ has $k$ bits in its binary representation, i.e. $2^{k-1} \leq n < 2^k$. Then $n^2$ has either $2k-1$ or $2k$ bits.

First we show that if $n$ is a term of the sequence, then $n^2$ has $2k-1$ bits. Suppose $n^2$ has $2k$ bits, i.e. $n^2 \geq 2^{2k-1}$. Then $2^{2k} - 1 - n^2 < 2^k - 1 - n$. This is rearranged as $n^2 - n + 2^k - 2^{2k} > 0$. Solving this quadratic inequality leads to $n > 2^k$ which contradicts the fact that $n$ has $k$ bits.

Thus $n^2 < 2^{2k-1}$ and $2^{2k-1} - 1 - n^2 < 2^k - 1 - n$. Solving this inequality and combining it with $n < \sqrt{2^{2k-1}}$ shows that $n$ must satisfy $\sqrt{2^{2k-1}} > n >  \frac{1}{2}+ \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.

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 = \sqrt{2^{2k-1}}$ and $b = \frac{1}{2} + \sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}$.

Using the identity $\sqrt{x} - \sqrt{y} = (x-y)/(\sqrt{x}+\sqrt{y})$ it follows that $a-b = -\frac{1}{2} + \frac{2^k - \frac{1}{4}}{\sqrt{2^{2k-1}}+\sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}} < -\frac{1}{2} + \frac{2^k}{\sqrt{2^{2k-1}} + \sqrt{2^{2k-1}-2^k}}$.

Since $k \geq 2$, $\sqrt{2^{2k-1}-2^k} = \sqrt{2^{2k-1}(1-2^{1-k})} \geq \sqrt{\frac{1}{2}}\ \sqrt{2^{2k-1}}$. This implies that $a-b < -\frac{1}{2} + \frac{2^k}{\frac{\sqrt{2}+1}{\sqrt{2}}\sqrt{2^{2k-1}}} = \frac{2\sqrt{2}}{\sqrt{2}+1} - \frac{1}{2} < 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. $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if $\sqrt{2^{2k-1}}-\lfloor\sqrt{2^{2k-1)}}\rfloor < a-b$ where $a-b$ is as defined above.

The criterion can be simplified as:
$\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$. This concludes the proof.$\blacksquare$

Note that $a-b \rightarrow \frac{1}{2}$ as $k \rightarrow \infty$, i.e. for large $k$, the fractional part of $\sqrt{2^{2k-1}}$ should be less than about $\frac{1}{2}$ in order for the integer part to be a term.

The numbers $k$ such that $\lfloor\sqrt{2^{2k-1}}\rfloor$ 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 \times 60166065 \times 10 = 33732769778928900 = 183664830^2$.

To see this, let us denote the decimal digits reversal of a number $n$ as $R(n)$.   Let $a = 56\times 10^{4+k}+106 + 6000\times (10^k-1)/9$ for $k\geq 0$. Then $R(a) = 601\times 10^{3+k}+65 + 6000\times (10^k-1)/9$. The number $10\times a\times R(a)$ can be written as $30360100\times (10^{k + 3} - 1)^2/9$ whose square root is $5510\times (10^{k + 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.

Sunday, December 30, 2018

Christmas lights ring oscillator

We set up a string of Christmas lights wrapped around a pine tree outside and plug it into an outlet with a dusk to dawn sensor so it will only turn on at dusk. After a windy day, some of the lights fell from the tree so we adjusted it in the evening. After adjustment, my son noticed that the lights turn on and off at a regular interval, which was strange since these lights are not flashing lights, but are supposed to be on all the time. It turns out one of the light bulb is too close to the light sensor on the outlet, thus tricking it to turn off since the outlet assumed it was dawn. Since it is now dark without the lights, the sensor assumes it is dusk and turns the light back on and so on and so on. Since there is a delay in the sensor, this resulted in the lights being turned on and off periodically. In essence, we have constructed a ring oscillator. A ring oscillator consists of a loop of an odd number of NOT logic gates. The number of stages and the delay in each stage of the logic gates determine the frequency of the oscillator. In our case, we have a single NOT gate represented by the dawn-to-dusk light sensor/outlet combination.

Sunday, May 20, 2018

An equation involving radicals

While browsing the internet, the following brainteaser popped up on the screen: find $x$ such that

$$\sqrt{x+15} + \sqrt{x} = 15$$

A straight forward approach is to square both sides, move the single term with radicals to one side and square again, and reducing terms to obtain a linear equation in $x$ whose solution gives the answer.

Here is another (somewhat simpler) way to solve this problem. First note that the left hand side is a increasing function of $x$ and at $x=0$ is equal to $\sqrt{15} < 15$, so there is a single real solution to the equation above.
If we set $x = y^2$ and $x+15 = (y+z)^2$, we get $15 = 2yz + z^2 = z(2y+z)$. The left hand side of the original equation then becomes:

$y+z +y = 2y+z = 15$. Combine this with the above it follows that $z = 1$ and $y = 7$. Thus the answer is $x = 49$.

In general, this method shows that the equation

$$\sqrt{x+a} + \sqrt{x} = b$$ where $b \geq 0$ and $b^2 \geq a$ has as the only real solution:

$$x = \left(\frac{b^2-a}{2b}\right)^2$$

For the case $a = b \geq 0$, this reduces to

$$x = \left(\frac{a-1}{2}\right)^2$$

which is an integer if $a$ is odd.

Monday, April 16, 2018

What is a slide rule for?

I was listening to Sam Cooke's classic song "Wonderful World" and thought of the line: "Don't know what the slide rule is for". When the song was released in 1960, the line was describing how disinterested the protagonist was about math and algebra, as the slide rule was a common tool for doing calculations. Today, that line would probably describe most young adults or younger, as the slide rule has not been used for calculations for many years with the rise of the calculator. When I was in high school, we used electronic calculators in our tests and exams, but out of curiosity my brother and I bought a slide rule anyway (they were still being sold in bookstores at the time, but disappeared soon after from the shelves). I was fascinated by how you can multiply two numbers merely by aligning the start of one ruler with the first number and reading off the result off the second number.  This is due a property of logarithm: log(ab) = log(a) + log(b). Thus multiplication is reduced to addition. By printing the numbers in logarithmic scale and lining up segment end-to-end (corresponding to addition), we achieve the operation of multiplication using a slide rule. Similarly, division can be done with a slide rule as it corresponds to subtraction. And it can do a lot more, such as trigonometry and taking square and cube roots. Accuracy was a problem, and they were soon supplanted by calculators which can compute to many digits of precision. As the song is continuously being covered by many artists, I wonder if the current audience would find the lyrics strange?

Wednesday, March 14, 2018

Primes of the form H(n,-k)-1

OEIS sequence A299145 lists the primes of the form $Q(n,k) = \sum_{i=2}^n i^k$ for $n \geq 2$ and $k> 0$. It is clear that except for the case $k =1$ and $n=2$ resulting in the prime $2$, we must have $n\geq 3$.
The sum $Q(n,k)$ is equal to $H(n,-k) - 1$ where $H(n,m) = \sum_{i=1}^n \frac{1}{i^m}$ is the generalized harmonic number of order $n$ of $m$. It is well known that $H(n,-k)$ is a polynomial of $n$ of degree $k+1$. In particular, Faulhaber's formula shows that
$$H(n,-k) = \frac{1}{2} n^k + \frac{1}{k+1}\sum_{j=0}^{\lfloor k/2 \rfloor} \left(\begin{array}{c} k+1\\2j\end{array}\right) B_{2j} n^{k+1-2j}$$
where $B_i$ is the $i$-th Bernoulli number.

$H(n,k)$ and thus $Q(n,k)$ can be written as a degree $k+1$ polynomial of $n$ with rational coefficients. The smallest denominator of this polynomial is found in OEIS A064538. In 2017, Kellner and Sondow showed that this is equal to $(k+1)\prod_{p\in S}$ where $S$ is the set of primes $p \leq \frac{k+2}{2+(k \mod 2)}$ such that the sum of the base $p$ digits of $k+1$ is $p$ or larger.

Since $H(1,-k) = 1$, this implies that $Q(1,k) = 0$ and thus $n-1$ is a factor of $Q(n,k)$. Since $n\geq 3$, if $n-1$ does not get cancelled out by a factor of the denominator, we would have a nontrivial factor of $Q(n,k)$ and thus $Q(n,k)$ is not prime. This implies that $Q(n,k)$ is prime only if $n-1$ is a divisor of a(k) in sequence A064538. Thus for each $k$ there is only a finite number of values of $n$ to check. This provides an efficient algorithm to find terms of this sequence by looking only for primes in the numbers $Q(n,k)$ where $n-1$ is a divisor of A064538(k). There are 45 such numbers with $1000$ or less digits.

Bernd C. Kellner, Jonathan Sondow, Power-Sum Denominators, Amer. Math. Monthly 124 (2017), 695-709.

Tuesday, February 20, 2018

Chaos in music

In an earlier post, I talked about fractals mentioned in the lyrics of a song. Today, I heard the song "Jurassic Park" by Al Yankovic, which mentions chaos theory, a related branch of mathematics that studies the unpredictable and complex behavior of dynamical systems, often manifested as sensitive dependence on initial conditions. On the other hand, musical compositions themselves can exhibit fractal and chaotic behavior [1,2].


[1] K J Hsü and A Hsü, "Self-similarity of the "1/f noise" called music," PNAS, vol. 88, no. 8, pp. 3507-3509, 1991.
[2] J. Beran, "Music - Chaos, Fractals, and Information," CHANCE, vol. 17, no. 4, pp. 7-16, 2004.

Monday, December 18, 2017

O, zero and eight

When my parents bought us our first computer, a Commodore VIC-20, in my early teens, I learned that to distinguish capital O with the digit zero, a diagonal line is put through the digit zero (also known as a slashed zero). This is due to the relatively low resolution computer fonts used in those days, where O is easily confused with 0 (but its use actually predates computers). On the other hand, some Scandinavian languages has something similar to a slashed zero in their alphabet, and the slashed zero can cause more problems than it solves. The use of the slashed zero is also useful when writing computer code using pen and paper, an activity that is becoming rare. Recently, I have not seen the use of slashed zero in word processing since given the number of pixels they have at their disposal, many fonts do not use it to represent the digit 0. In some fonts such as DejaVu Sans Mono and the font used in the Windows command prompt, a dotted zero is used to represent 0. Incidentally, for the Default font used in this blog, zero (0) looks almost identical to the lowercase letter "o".

The empty set (the set with zero elements) is denoted as {}, and is sometimes also denoted with a symbol similar to a slashed zero, but with the slash extending beyond the boundary of "0". This notation makes sense since in Zermelo-Fraenkel set theory the natural numbers are defined as sets with 0 being the empty set and the number n+1 defined as $n \cup \{n\}$, i.e. n+1 is the set obtained by augmenting the set n with a single element: the set consisting of the set n. In other words, 0 = {}, 1 = {{}}, 2 = {{},{{}}}, etc.

The use of a slashed zero is a good idea, but recently I found that it is causing problems for me. There is one place where I consistently see the use of a slashed zero and that is on credit card receipts. With advancing age and the onset of farsightedness, I have a hard time separating the slashed zero from the digit 8. When we go out to eat at a restaurant, the lighting is typically dim which exacerbates the problem and sometimes I have a hard time determining how much tip to leave and add it up correctly on the bill. I wish the receipt printer would not use the slash zero in their font (I don't think the dotted zero is much better either in this case).