Help with a university Problem

general
, ,
1

Hello all,

Today there was a contest held at my university, which featured 5 problems for a 3h contest.

My team performed poorly, especially because I’m not very used to “work under pressure” and I lack time to study some more theory behind some problems after contests are over… I’m slowly trying to change that and I will try to use some problems of this contest towards the goal of improving my abilities.

The problem was just this:

Given two positive numbers a and b, such that:

0 < a, b <= 191244368

We were asked to calculate the length of the cycle of the fraction a/b, where cycle is defined as a chain of repeated digits on the decimal expansion of the fraction.

For example, if a= 1 and b = 7, answer is 6, because:

1/7 = 0.142857 142857 …

where 142857 repeats for ever.

Any hints or ideas people can give me will be very helpful to me :slight_smile:

Thank you in advance,

Bruno

PS: I believe it might be somehow related to prime numbers, but, I’m really clueless…

1 Like
2

@kuruma :

EDIT :

<<1>> A cyclic number is an integer in which cyclic permutations of the digits are successive multiples of the number. The most widely known is 142857:

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428 and so on…

<<2>> As mentioned above ,Cyclic numbers are generated by the full reptend primes (frp), i.e., 7, 17, 19, 23, 29, 47, 59, 61, 97 etc. Eg : 1/7, 1/17, 1/19…so on.

Now, multiples of these fractions exhibit cyclic permutation:

1/7 = 0.142857 142857…

2/7 = 0.285714 285714…

3/7 = 0.428571 428571… and so on…

Your Test Case :

  • a=12741352 and b=137133904.
  • Now, factorizing b we have b = (2^4)*(8570869), where 8570869 is prime say p. Iff p is frp then :
  • Hence from point <<1>>, (k/p) will produce permutations of cyclic number produced by (1/p). Here, in your case k = 2^4. So, 1/((2^4)*(8570869)) = X(say), produce Cyclic number of length p-1 = 8570868.
  • Now, from point <<1>> or <<2>> , 12741352*X will produce again cyclic permutation of same cyclic numbers. Hence overall Cyclic number length = 8570868.
7 Likes
3

Thank you @bit_cracker007,

So, as far as I’ve understood, if I have a fraction of the form 1/p, where p is prime, the cycle length can be at most p-1, yes?

However, I still don’t see how I can generalize such thing for the cases where a != 1…

Shall I begin by factoring the denominator?

Bruno

4

Where were you dude all this time? Welcome back :slight_smile:

1 Like
5

Thanks bugkiller :slight_smile: I’ve been always here… “Lurking” from time to time… But, at the moment, I’m so busy with university that I just can’t keep up with being active here… Or at least, not as active as I was… But, I hope to return soon with more time, both to learn, and to set problems :smiley:

1 Like
6

Have a look again, this case has been explained in my 2nd point.

1 Like
7

@bit_cracker007,

I haven’t yet understood point 2 entirely, especially because I might be confused as how can I generalize the given idea of frp (full reptend primes) for the case of very large numbers…

For example, numbers:

a=12741352 and b=137133904

yield as answer 8570868.

I might be lacking some obvious mathematical background here, but, can you kindly guide me trough the above example so I can attempt to code a solution based on your tips, please? :slight_smile:

8

@kuruma >> Yeah man, expecting your problems in the contests :slight_smile: and same here buddy, semester exams, pi

ed off! All the best to you for the university stuff. :)
2 Likes
9

Thanks… for you as well :smiley:

By the way if you want to keep in touch, add me on gmail :slight_smile:
olivbruno8 at gmail dot com :wink: