Given r and n, find first n numbers of x where moving first digit of x to last gives x/r = y

Objective

Given input `r` and `n` find the first `n` natural numbers `x` such that if we rotate the first digit to the last place we obtain `x/r`.

You may assume that `2 <= r <= 9` and `1 <= n <= 65535`.

You may write a program which takes input from stdin or command-line arguments; or you may write a function which takes `r` and `n` as parameters. Output, however, should be to stdout. Output should be one line per value of `x`, formatted as `x/r=y`, in order of increasing `x`.

Your solution must be able to handle all valid cases within one minute on a reasonable desktop computer.

Test cases

Input: `4 5`
Output:

``````102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
``````

Input: `5 1`
Output: `714285/5=142857`

This is code-golf, so least bytes win. Winning answer will be accepted 4 weeks from now (2014-09-19).

Credits for this question go to my colleague, who allowed me to post this question here :)

-
The time restriction is tough with the amount of output required. According to `gprof`, one input case for my program spends less than half a second in my code, but takes around 80 seconds total, which I assume must be mostly blocking on output. – aschepler Aug 23 '14 at 2:38
Ah, I got around it by avoiding `printf`. – aschepler Aug 23 '14 at 19:58

Second version, probably further golfable, but with "proper" algorithm this time. In particular, it finishes within a few minutes with `r=4` and `n=65535`, but then again my computer is neither reasonable nor a desktop, so chances are this stays within a minute on other machines.

``````n#r=take n\$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
``````

It is based on the idea that `x=10^k*a + m`, where its first digit `0≤a≤9` is moved to the end to obtain `y=10*m+a`. A little maths reveals that `m` can be obtained as `a*(10^k-r)/(10*r-1)`, so we simply scan `a` over `[1..9]` for every `k` from 0 to infinity, and keep and print the first `n` results for which the above expression for `m` is integral.

The `fromIntegral` is required because `read`ing a list with `n` as one of its elements in `main`, in combination with the use of `n` in `take`, would force `r` to `Int` throughout, which results in nasty overflows with the big numbers in question. I could have used `genericTake`, but that requires an `import`.

This code also has the benefit of being almost trivial to expand to bases other than 10.

Input is read from `stdin`, the two values can be separated by any whitespace.

-
Your code should be shorter if you get rid of the backsticks – proud haskeller Aug 22 '14 at 9:53
@proudhaskeller: not sure because there are no parentheses around them to separate operator and operand without requiring spaces. – TheSpanishInquisition Aug 22 '14 at 10:02
I can't read Haskell, so I'm not entirely sure what you're doing. Will this solve `r = 5; n = 65535` within a minute? – Martin Ender Aug 22 '14 at 10:05
@MartinBüttner: I was waiting for that comment. Yes, it probably will, but not on my computer (or anyone else's right now, in fact). The problem needs a more advanced algorithm, I think. :( – TheSpanishInquisition Aug 22 '14 at 10:08
@TheSpanishInquisition But you ahould be able to replace `y`mod`10` with `mod y10`, which is a char shorter – proud haskeller Aug 22 '14 at 10:36

Pure Bash (no external utilities), 80 bytes

``````for((;++x,c<\$2;));{
y=\$[10#\${x:1}\${x:0:1}]
((y*\$1==x))&&echo \$x/\$1=\$y&&((c++))
}
``````

Note bash only does integer arithmetic and not floating point, so we check if `x == y * r` instead of `x / r == y`. Also multiplication should generally be faster. Still, this is nowhere near meeting the performance requirement.

Output:

``````\$ ./rotdiv.sh 4 5
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
\$ ./rotdiv.sh 5 1
714285/5=142857
\$
``````
-

C 468

``````#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}
``````

(Some newlines not counted in the byte count have been added above to eliminate scroll bars. Yes, the final newline is counted.)

Expects arguments on the command line, and assumes standard output accepts ASCII. Runtime is O(number of bytes output) = O(n*n).

No, I can't use `printf`. That takes too much time and pushes the program over the minute limit on my desktop. As it is, some test cases take about 30 seconds.

The algorithm treats the output as strings, not numbers, since they quickly get enormous, and there are strong patterns in the output.

Somewhat ungolfed:

``````#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
for (int i=0; i <= repeats; ++i)
fputs(num, stdout);
printf("/%c=", '0'+r);

/* Assume the repeated num is a solution. Just move the first
digit and skip any resulting leading zeros. */
const char* num_tail = num;
++num_tail;
while (*num_tail=='0')
++num_tail;
fputs(num_tail, stdout);
while (repeats--)
fputs(num, stdout);
printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
r = atoi(argv[1]);
int n = atoi(argv[2]);
int q = 10*r-1;
int d = 0;

/* Populate the strings in sol[]. */
while (d++<9) {
int p = r*d;
char* sol_str = sol[d];

/* Do the long division p/q in decimal, stopping when the remainder
is the original dividend. The integer part is always zero. */
do {
p *= 10;
*sol_str++ = p/q + '0';
p %= q;
} while (p != r*d);
}

d = 1;
int repeats = 0;
int r5x7_repeats = 0;
while (n--) {
if (r==5 && r5x7_repeats<6) {
show_line(x[7], 7*repeats + r5x7_repeats);
} else {
if (r==5 && d==7)
show_line(x[d], 7*repeats + 6);
else
show_line(x[d], repeats);
if (++d > 9) {
d = 1;
++repeats;
r5x7_repeats = 0;
}
}
}
}
``````

Proof

that the program solves the problem:

(In the proof, take all operators and functions to be the real mathematical functions, not the computer operations that approximate them. `^` denotes exponentiation, not bitwise xor.)

For clarity, I'll use a function `ToDec` to describe the ordinary process of writing a number as a sequence of decimal digits. Its range is the set of ordered tuples on `{0...9}`. For example,

``````ToDec(2014) = (2, 0, 1, 4).
``````

For a positive integer `n`, define `L(n)` to be the number of digits in the decimal representation of `n`; or,

``````L(n) = 1+floor(log10(n)).
``````

For a positive integer `k` and a non-negative integer `n` with `L(n)<k`, define `Rep_k(n)` to be the real number obtained by adding zeros in front of the decimal digits of `n`, if necessary to get `k` digits total, and then infinitely repeating those `k` digits after the decimal point. E.g.

``````Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...
``````

Multiplying `Rep_k(n) * 10^k` gives the digits of `n` before the decimal point, and the (zero-padded) digits of `n` infinitely repeated after the decimal point. So

``````Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)
``````

Given a positive integer `r`, suppose `x` is a solution to the problem, and

``````ToDec(x) = ( x_1, x_2, ..., x_k )
``````

where `x_1 != 0` and `k = L(x)`.

To be a solution, `x` is a multiple of `r`, and

``````ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).
``````

Applying the `Rep_k` function gives a nice equation:

``````10*Rep_k(x) = x_1 + Rep_k(x/r)
``````

Using its closed form from above,

``````10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)
``````

`x_1` must be in the set `{1 ... 9}`. `r` was specified to be in the set `{2 ... 9}`. Now the only question is, for what values of `k` does the above formula for `x` give a positive integer? We'll consider each possible value of `r` individually.

When `r` = 2, 3, 6, 8, or 9, `10r-1` is 19, 29, 59, 79, or 89, respectively. In all cases, the denominator `p = 10r-1` is prime. In the numerator, only `10^k-1` can be a multiple of `p`, which happens when

``````10^k = 1 (mod p)
``````

The set of solutions is closed under addition and under subtraction that does not result in a negative number. So the set comprises all the multiples of some common factor, which is also the least positive solution for `k`.

When `r = 4` and `10r-1 = 39`; or when `r = 7` and `10r-1 = 69`, the denominator is 3 times a different prime `p=(10r-1)/3`. `10^k-1` is always a multiple of 3, and again no other factor in the numerator can be a multiple of `p`, so again the problem reduces to

``````10^k = 1 (mod p)
``````

and again the solutions are all the multiples of the least positive solution for `k`.

[Not finished...]

-

Python - 91 90

Here's a first shot:

``````r,n=input();i=1
while n:
if int(`i`[1:]+`i`[0])*r==i:print'%d/%d=%d'%(i,r,i/r);n-=1
i+=1
``````

Edit: Ok, it's probably way to slow to meet the required 1-minute time limit for 65K numbers.

-
Have you tested this against the performance requirement? – Peter Taylor Aug 22 '14 at 9:13
I have my doubts that this will find 65k such numbers before the sun explodes. – Martin Ender Aug 22 '14 at 9:13

JavaScript - 145

``````function f(a,b){for(d=0;d<b;d++)for(i=1;;i++){c=i/a;if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))console.log(i+'/'+a+'='+c)}}
``````

not golfed:

``````function f(a,b){
for(d=0;d<b;d++) //loop for the right amount
for(i=1;;i++){ //iterating loop
c=i/a; //actual result of the division
if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))
console.log(i+'/'+a+'='+c)
}
}
``````
-
I can't get this to work at all, but even if it would, I doubt it would meet the performance requirement. – Martin Ender Aug 22 '14 at 11:07
@MartinBüttner it works perfectly fine for me. it could be that it does not meet the performance requirements but i the computer i am right now is pretty weak... What did you do to make this piece of code work? – Armin Aug 22 '14 at 11:25
Copied it into the console and appended `(5,4)`. The reason it won't work is that the numbers grow very large. a) A lot larger than a number in JS can represent accurately and b) way too large as that it would be feasible to iterate through all numbers to get there. – Martin Ender Aug 22 '14 at 11:27

Python 3 - 223 179 bytes

Python implementation of TheSpanishInquisition's solution:

``````r,n=map(int,input().split());k=0
while 1:
for a in range(1,10):
D,M=divmod(a*(10**k-r),10*r-1)
if M==0:
print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
if n==0:exit()
k+=1
``````

Run:

• `python3 <whatever you named it>.py`
• Takes input on stdin
• Input space separated

Output:

``````\$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128
``````

Findings:

https://oeis.org/A092697 is the first value for each r.

It seems that only certain values of k produce answers, and that the interval is regular. E.g. for r = 4:

``````Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]
``````

The intervals are:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 seems to be an anomaly, as for most values of r, there are clumps of 9, 5 forms clumps of 9 and 1 (with only a = 7 working), see below)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

This forms https://oeis.org/A094224.

Using these values, a more efficient version can be built:

``````import math

def A094224(n):
return [18,28,6,6,58,22,13,44][n-2]

r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
for a in range(1,10):
D,M=divmod(a*10**k-a*r,10*r-1)
if M==0:
print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
if n==0:exit()
k+=A094224(r)
``````

However, I can't (yet) prove that this continues mathematically.

Results for r = 5:

``````0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]
``````
-
Have you tested it with input `9 65535`? – Peter Taylor Aug 22 '14 at 13:29
I should probably use `unsigned long long` for that, and make it multicore to do that in one min. – matsjoyce Aug 22 '14 at 13:36
If `unsigned long long` is 64 bits, it's not big enough. – Peter Taylor Aug 22 '14 at 13:38
True, I've switched to @TheSpanishInquisition's solution and used python instead. – matsjoyce Aug 22 '14 at 14:29