4
$\begingroup$

Does there exist a number $n$ such that all numbers $n, 2n, 3n, 4n, \dots, 2000n$ have the same multi-sets of digits except zeroes?

(Having the same multi-sets of digits excepts zeroes means having equal number of ones, twos, ... , nines in the decimal expansion.)

A related question was already asked on MathSE, but the answers there does not provide an approach suitable for bigger numbers like 2000.

$\endgroup$
  • $\begingroup$ This question was asked here in a bizarre way: instead of asking a new question, the OP changed his old question completely. I didn't notice that and after having solved the problem I found the question disappeared. But I believe it is interesting. And since the OP does not post the question, I've decided to ask - and answer - it myself. $\endgroup$ – zhoraster Nov 23 '15 at 16:29
  • 3
    $\begingroup$ How about $n=0$? $\endgroup$ – mvw Nov 23 '15 at 16:31
  • $\begingroup$ Biggest coincidence ever. I was checking this out just a few minutes back. $\endgroup$ – rah4927 Nov 23 '15 at 16:35
  • 1
    $\begingroup$ If 2n and n have the same digits except zero than 20n, 200n, 2000n, and 20000000000000000000n will. If by "bigger" you mean "multiplied by higher powers of 10" the approach for bigger numbers wasn't provided because it is utterly trivial. $\endgroup$ – fleablood Nov 23 '15 at 16:38
  • 1
    $\begingroup$ I have yet to find a solution that utilizes $10$ is a primitive root modulo $7^k$. $\endgroup$ – rah4927 Nov 23 '15 at 16:42
11
$\begingroup$

Suppose $N>2000$ is an integer such that the period length of the (eventually) repeating $\frac1N$ equals $N$. Then in computing the decimal expansion all remainders $1,\ldots,N-1$ occur at some place. Then the fractions $\frac1N,\frac2N,\ldots, \frac{2000}N$ turn out to lead to the very same period, merely shifted. In this situation, we have $\frac1N=\frac n{10^{N-1}-1}$ for some $1\le n< 10^N-1$ and conclude that $n,2n,\ldots,2000n$ indeed are obtained by rotating the digit sequences suitably (taking an appropriate number of leading zeroes into account).

(Actually, it would be sufficient that the remainders $1,2,\ldots,2000$ occur during the computation of the period, so the period length might be smaller than $N$.)

The question is: Do such $N$ exist? Primes are good candidates (for any other $N$, the order of $10$ cannot exceed $\phi(N)$). So for which primes $N$ is $10$ of order $N-1$? One such prime is $2017$ and that is $>2000$, thius solving the concrete problem - or rather $$ n=\frac{10^{2016}-1}{2017}=\underbrace{4957858205\ldots233019335647}_{2013\text{ digits}} $$ is. Intriguingly, each of the digits $1,2,4,5,7,8$ occurs $202$ times, each of $3,6,9$ occurs $201$ times in that $n$. In fact, it turns out that $2017$ is the smallest prime $>2000$ with this property. As additionally, $\phi(n)<2000$ for all composites $<2017$, we see that $2017$ is the smallest $N$ for which the above construction works. However, this does not completely rule out that smaller $n$ exist (where the $kn$ only "accidentally" have the same digit statistics).

See also sequence Full reptend primes in OEIS.

$\endgroup$
  • $\begingroup$ Nice. Didn't expect that $2017$ works already. $\endgroup$ – zhoraster Nov 23 '15 at 16:59
  • $\begingroup$ @mvw Darn, why would you even check such a thing? :) $\endgroup$ – Hagen von Eitzen Nov 23 '15 at 17:09
  • $\begingroup$ Checking is next. Then I might start trying to understand how it works. :-) $\endgroup$ – mvw Nov 23 '15 at 17:11
  • $\begingroup$ @mvw, you can check my number (it is for a different $p$, but I wrote all digits for your convenience :) ). $\endgroup$ – zhoraster Nov 23 '15 at 17:15
8
$\begingroup$

The answer is positive. Moreover, there exists a number $n$ such that additionally all numbers $2n,3n,\dots,2000n$ are obtained from $n$ by cyclic permutation of digits (naturally, we need to add some zeroes before $n$ for that). Here is this number:

0004330879168471199653529666522304027717626678215677782589865742745777392810740580337808575140753572975313988739714161974880900822867042009527934170636639237765266349068860978778692074491121697704634040710264183629276743178865309657860545690775227371156344737981810307492420961455175400606323083585967951494153313122563880467734950194889562581203984408834993503681247293200519705500216543958423559982676483326115201385881333910783889129493287137288869640537029016890428757037678648765699436985708098744045041143352100476396708531831961888263317453443048938934603724556084885231702035513209181463837158943265482893027284538761368557817236899090515374621048072758770030316154179298397574707665656128194023386747509744478129060199220441749675184062364660025985275010827197921177999133824166305760069294066695539194456474664356864443482026851450844521437851883932438284971849285404937202252057167605023819835426591598094413165872672152446946730186227804244261585101775660459073191857947163274144651364226938068427890861844954525768731052403637938501515807708964919878735383282806409701169337375487223906453009961022087483759203118233001299263750541359896058899956691208315288003464703334776959722823733217843222174101342572542226071892594196621914248592464270246860112602858380251190991771329579904720658293633607622347336509311390212213079255088783022953659592897358163707232568211346903421394543092247726288436552620181896925075790385448245993936769164140320485058466868774361195322650498051104374187960155911650064963187527067994802944997834560415764400173235166738847986141186660892161108705067128627111303594629709831095712429623213512343005630142919012559549588566478995236032914681680381117366825465569510610653962754439151147682979644867908185361628410567345171069727154612386314421827631009094846253789519272412299696838458207016024252923343438718059766132524902555218709398007795582503248159376353399740147249891728020788220008661758336942399307059333044608055435253356431355565179731485491554785621481160675617150281507145950627977479428323949761801645734084019055868341273278475530532698137721957557384148982243395409268081420528367258553486357730619315721091381550454742312689475963620614984841922910350801212646167171935902988306626245127760935469900389779125162407968817669987007362494586401039411

But how to find it?

Let us call a number $n$ $k$-cyclic if all numbers $2n,3n,\dots,kn$ are obtained from $n$ by cyclic permutation of digits. For example, $142857$ is $6$-cyclic: $2\cdot 142857 = 285714$, $3\cdot 142857 = 428571$, $4\cdot 142857 = 571428$, $5\cdot 142857 = 714285$, $6\cdot 142857 = 857142$.

The crucial step is the following observation (proof is available on request):

Let $p$ be a prime number such that $10$ is a primitive residue modulo $p$. Then the period of the fraction $1/p$ is $(p-1)$-cyclic.

For example, $10$ is primitive root modulo $7$, and from $1/7 = 0.(142857)$ we get that $142857$ is $6$-cyclic, which we saw already.

So we are left to find a prime number $p>2000$ such that $10$ is a primitive root modulo $p$. There is a useful Chebyshev theorem:

If $p=4q+1$ is prime, where $q$ is prime and $q = 2 \pmod 5$, then $10$ is a primitive root modulo $10$.

Now the smallest prime number greater than $2000$ and satisfying the Chebyshev theorem is $2309 = 4\cdot 577-1$. Therefore, the period of $1/2309 = 0.0004330879\dots$ is $2308$-cyclic (hence, $2000$-cyclic). This period is written above.

$\endgroup$
  • $\begingroup$ So if Artin's conjecture holds true, we can replace $2000$ by any other number(as noted by someone on this same problem on aops). $\endgroup$ – rah4927 Nov 23 '15 at 17:46
  • $\begingroup$ I just wish Artin's conjecture would be proved. I want to use it in many contest problems but can't because of its still being a "conjecture". $\endgroup$ – rah4927 Nov 23 '15 at 17:47
1
$\begingroup$

I told my friend Ruby how to check the numbers by Hagen, zhoraster and two test numbers by me (n=4212345, n=0). She did the check and got:

n digits:
[0:198, 1:202, 2:202, 3:201, 4:202, 5:202, 6:201, 7:202, 8:202, 9:201]
OK - congrats!

n digits:
[0:227, 1:231, 2:231, 3:231, 4:231, 5:231, 6:231, 7:231, 8:231, 9:230]
OK - congrats!

n digits:
[0:0, 1:1, 2:2, 3:1, 4:2, 5:1, 6:0, 7:0, 8:0, 9:0]
error:
n_2 digits:
[0:1, 1:0, 2:1, 3:0, 4:2, 5:0, 6:1, 7:0, 8:1, 9:1]

n digits:
[0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0]
OK - congrats!

We then did a little search for numbers of the form $(10^{k-1}-1)/k$ for $k$ from $1$ to $3000$. See the log.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.