Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 :)

share|improve this question
    
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 at 2:38
    
Ah, I got around it by avoiding printf. –  aschepler Aug 23 at 19:58

6 Answers 6

Haskell, 182 179

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.

share|improve this answer
    
Your code should be shorter if you get rid of the backsticks –  proud haskeller Aug 22 at 9:53
    
@proudhaskeller: not sure because there are no parentheses around them to separate operator and operand without requiring spaces. –  TheSpanishInquisition Aug 22 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 Büttner Aug 22 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 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 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
$ 
share|improve this answer

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

    /* Output the answers. */
    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...]

share|improve this answer

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.

share|improve this answer
1  
Have you tested this against the performance requirement? –  Peter Taylor Aug 22 at 9:13
2  
I have my doubts that this will find 65k such numbers before the sun explodes. –  Martin Büttner Aug 22 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)
        }
}
share|improve this answer
    
I can't get this to work at all, but even if it would, I doubt it would meet the performance requirement. –  Martin Büttner Aug 22 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 at 11:25
1  
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 Büttner Aug 22 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]
share|improve this answer
2  
Have you tested it with input 9 65535? –  Peter Taylor Aug 22 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 at 13:36
1  
If unsigned long long is 64 bits, it's not big enough. –  Peter Taylor Aug 22 at 13:38
    
True, I've switched to @TheSpanishInquisition's solution and used python instead. –  matsjoyce Aug 22 at 14:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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