2
\$\begingroup\$

Here, x (supplied as input) and n (the result of your computation) are both positive integers. n * x = n shifted. Find n.

Here's an example of shifting:

123456789 -> 912345678
abcdefghi -> iabcdefgh (letters = any 0~9 digit)
123       -> 312

Shifting only happens once to the right. Shifting left, e.g.

123456789 -> 234567891 

is not a valid shifting.

Rules

  • Preceding zeros count after shifting. If the number is 10 and is multiplied by 0.1 (0.1 isn't a valid input), the result is 1, which isn't equal to 01 (10 after shifting).
  • If your number only has one digit, the shifted result is your number:
1 -> 1
4 -> 4
9 -> 9
  • Given enough time and resources, your program/function should work for any x input, but you only have to support x in the range [1,9] without timing out on Try It Online.

Test cases

For more test cases, this is OEIS A092697.

1 -> 1 (1 * 1 = 1 shifted.)

9 -> 10112359550561797752808988764044943820224719
(In this test case, x = 9 and n = 10112359550561797752808988764044943820224719.
n shifted = n * x =              91011235955056179775280898876404494382022471)

6 -> 1016949152542372881355932203389830508474576271186440677966
```
\$\endgroup\$
6
  • 7
    \$\begingroup\$ Can we have some more test cases / a fully working reference program? I'm still a little unsure of what the program needs to do. \$\endgroup\$
    – lyxal
    Feb 18 '20 at 10:37
  • \$\begingroup\$ @Lyxal Assuming \$x\le9\$, I think the longest output is for \$x=6\$, for which I've found 1016949152542372881355932203389830508474576271186440677966. \$\endgroup\$
    – Arnauld
    Feb 18 '20 at 11:49
  • \$\begingroup\$ Is the task actually possible for any input 10 or bigger? If I'm understanding right your rule about leading zeroes, the shifted value always has the same number of digits as the original, where the multiplied value has more digits in this case. \$\endgroup\$
    – xnor
    Feb 18 '20 at 11:49
  • 3
    \$\begingroup\$ This is oeis.org/A092697. Or, rather, the smallest possible outputs are in the sequence. I found this by Googling the large number given for x=9. One formula given says the output is x*(10^m-1)/(10x-1) for the smallest m that makes this a whole number. \$\endgroup\$
    – xnor
    Feb 18 '20 at 12:18
  • 4
    \$\begingroup\$ Just to be clear, the problem with the current spec is Given enough time and resources, your program/function should work for any x input, since the sequence is apparently not defined for \$x>9\$. \$\endgroup\$
    – Arnauld
    Feb 18 '20 at 12:37
7
\$\begingroup\$

Python 2, 31 bytes

lambda x:10**1045044/(10*x-1)*x

Try it online!

Produces enormous million-digit numbers. Uses the formula from the OEIS page, x*(10^m-1)/(10*x-1). But, instead of using the smallest possible m for the given x, we hardcode m=1045044, which works for each x from 1 to 9. (I'm assuming only these x need to be supported, because bigger ones are impossible.)

We need an m that's divisible by the order of 10 modulo 10*x-1. So, to get one that works for all x, we take the least common multiple (LCM) of the orders, giving m=1045044.

x order
-----
1 1
2 18
3 28
4 6
5 42
6 58
7 22
8 13
9 44

We save a few bytes by doing 10^m/(10*x-1) instead of (10^m-1)/(10*x-1), since Python 2's floor division cuts off the remainder and gives the same result, as long we move the *x after the division.

Despite how the massive the results are, TIO can in fact compute them for every x from 1 to 9 without timing out. Validating the rotating property of an output string-wise takes longer, but if you set validate=True in the TIO link and the limit to a single x, this also completes before timing out. I've also validated all the results on my machine.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js),  54 48  44 bytes

Saved 4 bytes thanks to @xnor

Takes input as a BigInt. Based on the formula given in A092697.

f=(x,m=t=10n)=>~-m%(q=t*x-1n)?f(x,m*t):m/q*x

Try it online!


JavaScript (Node.js),  165 153  151 bytes

Takes input as a BigInt and performs a recursive search.

f=(x,n='',i=-1)=>+n[[d,...a]=[...x*BigInt(n)+''],s=a.join``+d,0]&&n==s?o=n:n.slice(0,i++)==s.slice(-i,-1)&i<60&&([...2**29+'4'].some(k=>f(x,k+n,i)))&&o

Try it online!


NB: Both solutions assume \$1\le x\le9\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ It looks like you can avoid aliasing p, and not bother decrementing before the division: Try it online! \$\endgroup\$
    – xnor
    Feb 18 '20 at 13:38
3
\$\begingroup\$

Wolfram Language (Mathematica), 42 bytes

#(10^MultiplicativeOrder[10,a=10#-1]-1)/a&

Try it online!

xnor's method n-shifted my bytes...

Wolfram Language (Mathematica), 24 bytes

#(10^1045044-1)/(10#-1)&

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ @ExpiredData Yes, I noticed xnor's answer, which makes this challenge trivial. I'll post it as a second approach \$\endgroup\$
    – ZaMoC
    Feb 18 '20 at 13:40
  • \$\begingroup\$ I don't know Mathematica, but is the a short floor-division operator that you replace the division with use to avoid decrementing -1 after the 10^1045044? \$\endgroup\$
    – xnor
    Feb 18 '20 at 13:55
  • \$\begingroup\$ Also, 29! should work for the constant, but this surely would make the code take too long to run. \$\endgroup\$
    – xnor
    Feb 18 '20 at 13:59
3
\$\begingroup\$

Jelly, 13 bytes

⁵×’⁵*“ÐṂ+’¤:×

Try it online! (The 1045044 digits do not fit within TIO's output)

An implementation of xnor's LCM method.

⁵×’⁵*58!$¤:× works in theory for 12, but there's no chance of calculating results with \$58!\$ digits within 60s using Jelly.

⁵×’⁵*“ÐṂ+’¤:× - Link: integer,    x
⁵             - 10                10
 ×            - multiply          10x
  ’           - decrement         10x-1
          ¤   - nilad followed by link(s) as a nilad:
   ⁵          -   10              10
     “ÐṂ+’    -   1045044         1045044
    *         -   exponentiate    10^1045044
           :  - integer division  10^1045044//(10x-1)
            × - multiply          10^1045044//(10x-1)*x
\$\endgroup\$
0
\$\begingroup\$

05AB1E (legacy), 12 bytes

T*<•GIs•°s÷*

Try it online!

T*             - Multiply input by 10 
  <            - subtract 1 
   •GIs•°      - 10**1045044
         s÷    - Integer divide
           *   - Multiply by input again 

Port of xnor's answer

\$\endgroup\$
4
  • 1
    \$\begingroup\$ N.B. It computes (as required) but the answer does not fit in TIO's output :D \$\endgroup\$ Feb 18 '20 at 13:59
  • \$\begingroup\$ Actually the answer is incorrect, and I'm not sure why - for x=9 the result should start 101123595... (see here) \$\endgroup\$ Feb 18 '20 at 14:22
  • \$\begingroup\$ is it just the integer division? m=43 seems to work :/ \$\endgroup\$ Feb 18 '20 at 14:27
  • 1
    \$\begingroup\$ ^ or 44 even, sorry. \$\endgroup\$ Feb 18 '20 at 15:01