# 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. Aug 23, 2014 at 2:38
• Ah, I got around it by avoiding printf. Aug 23, 2014 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 Aug 22, 2014 at 9:53
• @proudhaskeller: not sure because there are no parentheses around them to separate operator and operand without requiring spaces. Aug 22, 2014 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? Aug 22, 2014 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. :( Aug 22, 2014 at 10:08
• @TheSpanishInquisition But you ahould be able to replace ymod10 with mod y10, which is a char shorter Aug 22, 2014 at 10:36

# 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);
}

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 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? Aug 22, 2014 at 13:29
• I should probably use unsigned long long for that, and make it multicore to do that in one min. Aug 22, 2014 at 13:36
• If unsigned long long is 64 bits, it's not big enough. Aug 22, 2014 at 13:38
• True, I've switched to @TheSpanishInquisition's solution and used python instead. Aug 22, 2014 at 14:29