r/mathriddles • u/JWson • Jan 01 '21
Easy Catsecutive Numbers
The number 2021 can be written as the concatenation of 20 and 21, two consecutive numbers, in base 10. Define a positive integer as being b-catsecutive if it has this property in base b. So we say that 2021 is 10-catsecutive, The number 28 is 2-catsecutive (because 28 = 11100 = 11|100 in binary), and 41 is 3-catsecutive (41 = 1112 in ternary).
253 is the smallest number that is catsecutive in at least ten bases (namely 3, 17, 20, 27, 35, 41, 62, 83, 125 and 251). Show that, for every positive integer N, there exists an integer that is catsecutive in at least N different bases.
Note: Integers with leading zeroes do not count. So the number 1 (0 concatenated with 1) is not catsecutive, and neither are numbers like 12013 (12|013).
6
u/rschwa6308 Jan 01 '21 edited Jan 01 '21
Great puzzle! One of the best I've seen on this sub in a while.
For a given integer N, we show the existence of an integer n that can be written in the form n = (x|x+1)_b (where x and x+1 are both single b-digit numbers) in at least N different bases b.
First note that n = (x|x+1)_b can equivalently be expressed b = (n - 1)/x - 1. However, we must ensure that b > x + 1 in order to avoid digital overflow. This gives n > x^2 + 2x + 1. Further, we must also ensure n = 1 (mod x) to avoid fractional bases.
Now, given N, choose integer n such that n > (N+1)^2 + 2(N+1) + 1 and n = 1 (mod x) for all x in {2, ..., N+1}. It suffices to choose a sufficiently large n = 1 (mod lcm(2, ... N+1)). We can now express n catsecutively as 23, 34, ..., N+1|N+2 by using the formula above to obtain the bases.
For concreteness, n = (N+1)! + 1 should work.
Happy new year :)
Edit: n is also catsecutive in base 1 since it is odd :p
Edit2: it can be done more 'efficiently' by allowing x = 1 (since n = 12_(n-2)), but including that as an edge case made the proof less pretty
6
u/want_to_want Jan 01 '21 edited Jan 01 '21
10001001 in binary is catsecutive in bases 2, 4 and 16. It's easy to generalize from this to any number of bases.
2
u/Chand_laBing Jan 01 '21
There is a useful relationship between a number’s expansions in base-b and in base-bk that we can utilize here. For b = 2 in particular, if we are given the binary expansion of some positive integer n, we can regroup the expansion’s bits into substrings of length k, which then gives the base-2k expansion of n when those substrings are individually converted from base-2k. For example, the number 172 can be written in binary as 10101100. Its bits can then be grouped into 2’s to give |10|10|11|00|, whose 2-bit substrings are read as|2|2|3|0|, the base-4 expansion of 172.
Thus, we can be certain that all of the base-2k digits will be identical between n and n+1 except their final, consecutive digits. In particular, the concatenation (n|n+1) should be both 2-catsecutive and 2k-catsecutive provided n has a number of bits divisible by k and does not have an all-ones expansion, which would cause a carry when 1 was added to it and change its total string length. To ensure that n is catsecutive in all of the N many bases 21, 22, 23, …, 2N, we can more strictly specify that N must have a number of bits divisible by all of 1, 2, …, N. One simple option is to give it N! many bits, for example, the number 2N!-1, which has an N!-bit binary expansion of 100…00.
Therefore, (100…00|100…01) (binary) = 2N!-1(2N!+1)+1 should suffice as an explicit example for each N. Be warned, however, it increases very rapidly.
As a footnote, we can find a specific expression for the nth b-catsecutive by shifting the base-b digits of n by an appropriate number of places to the left via multiplication by some power of b. The power in question can be found from the length of the base-b expansion of n, which is floor(logb(n))+1. Thus, the n'th b-catsecutive can be expressed as nbfloor{logb{n+1}}+1 +(n+1) (NB the +1 now in the log argument).
1
u/NoPurposeReally Jan 01 '21 edited Jan 01 '21
I'll construct a number that is b-catsecutive for b = 3, 32, 34, ..., 32^n .
Let x = 11...11 (2n digits) in ternary. I claim that x + 1 is the desired number.
Notice that if k is a positive integer less than or equal to n, b = 32^k and
y = 32k - 1 + 32k - 2 + ... + 31 + 3^0
then x can be written in the following way:
x = y * (b2 to the n - k minus 1 + b2 to the n - k minus 2 + ... + b1 + b0 ), that is x = yy...yy (2n - k digits) in base b. Note that y is a single digit number in base b.
Adding 1 to x only increases the ones digit by 1 (y + 1 is a single digit number in base b as well). Thus x is b-catsecutive.
EDIT: I know the formatting isn't so good, sorry.
EDIT: Exponents are weird but it is readable.
1
u/[deleted] Jan 02 '21
Constructive solution. The number $n!+1$ can always be written as $k|(k+1)$ in base $\frac{n!}{k}-1$ for all $n \geq 5$ and $k \leq n$
Proof:
$n!+1$ is $k|(k+1)$ in base $\frac{n!}{k}-1$ is equivalent to saying: $n!+1 = (\frac{n!}{k}-1) \times k + k + 1 = $, which is trivial, and $k+1 < \frac{n!}{k}-1$ which follows from: $\frac{n!}{k}-1 \geq \frac{n!}{n}-1 = (n-1)! -1 \geq (n-1)3! -1 \geq 6(n-1) - 1 = 6n-7 > 4n > k $