# 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 main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words


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 reading 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 ymod10 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; int main(int c,char**v){r=atoi(v);int n=atoi(v),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*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 is unused. Otherwise, sol[d] is the repeating digits in the decimal representation of (r*d)/(10*r-1). */ char sol; int main(int argc, char** argv) { r = atoi(argv); int n = atoi(argv); 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); } /* Output the answers. */ d = 1; int repeats = 0; int r5x7_repeats = 0; while (n--) { if (r==5 && r5x7_repeats<6) { show_line(x, 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)*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 
6 []
7 []
8 []
9 []
10 []
11 
12 []
13 []
14 []
15 []
16 []
17 
18 []
19 []
20 []
21 []
22 []
23 
24 []
25 []
26 []
27 []
28 []
29 
30 []
31 []
32 []
33 []
34 []
35 
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