Cyclic Numbers
Carlos Bermejo
I'm new in this group and i don't know is this is an old thing
for you all. If so, i apologyze (also for my english)...
Cyclic numbers are positive integers of a given number of
digits such that, when multiplying them by another integer
between 1 and its number of digits, you obtain the same
digits in the same order but rotated.
As an example i'll give you this cyclic number:
0588235294117647
You can see that:
0588235294117647 x 2 = 1176470588235294 (note the rotation)
0588235294117647 x 3 = 1764705882352941
...
0588235294117647 x 16 = 9411764705882352
The fact is that doesn't exist such numbers for every numbers
of digits. The smallest cyclic number has 6 digit. The questions
are:
1. Can you find it?
2. If so, can you find a method (not brute-force) to find
cyclic numbers of any number of digits?
3. And if so, can you provide a math prove of it?
I only have the solution for the two first ones
Nice thinking...
CArlos
Amit Gal
here is a mathematical proof of a method to find cyclic numbers.
it seems that the converse of this method is also true (i.e. that every
cyclic number is a multiple of such generated cyclic number) but I not
prove it here.
suppose k is prime number. then the number 1,2 .... k-1 form a group
under multiplication modulo k.
suppose this group is cyclic and 10 (mod k) is its generator.
then 1/k is represented by 0.a1a2a3a4.....ak-1a1a2a3...ak-1....
and the number a1a2....ak-1 is cyclic.
proof: let p=a1a2....ak-1 and we want to prove it is cyclic.
let a be a number from 1 to k-1.
a*p = (10^k-1)*(a*p/(10^k-1))
but p/(10^k-1) is 0.a1a2...ak-1.....= 1/k.
and since a = 10^r(mod k) for some r then
a*p/(10^k-1) = a1a2...ar.ar+1...ak-1a1a2a3...ak-1.....
but because of the modulus we can ignore the integer part
and write a*p/(10^k-1) = 0.arar+1...ak-1a1a2a3....
and thus a*p = arar+1...ak-1a1a2...ar-1 which is a rotation of p
and this proves the statement.
Ed Murphy
Carlos Bermejo <jc...@tid.es> wrote:
> 0588235294117647
Corresponding to 1/17 = 0.0588235294117647 <repeat ad infinitum>
> 0588235294117647 x 2 = 1176470588235294 (note the rotation)
> 0588235294117647 x 3 = 1764705882352941
> ...
> 0588235294117647 x 16 = 9411764705882352
Corresponding to 2/17 through 16/17.
> The fact is that doesn't exist such numbers for every numbers
> of digits. The smallest cyclic number has 6 digit. The questions
> are:
> 1. Can you find it?
142857 (corresponding to 1/7).
> 2. If so, can you find a method (not brute-force) to find
> cyclic numbers of any number of digits?
As you note earlier, there isn't always one for a given number of digits.
However, consider 076923 (corresponding to 1/13): Every multiple of it
from 2 to 12 is either a rotation of the digits 076923 or a rotation of
the digits 153846 (corresponding to 2/13). Thus 1/13 is 2-cyclic, 1/7
is 1-cyclic, 1/37 is 12-cyclic, etc.
Torben AEgidius Mogensen
Carlos Bermejo <jc...@tid.es> writes:
>I'm new in this group and i don't know is this is an old thing
>for you all. If so, i apologyze (also for my english)...
>Cyclic numbers are positive integers of a given number of
>digits such that, when multiplying them by another integer
>between 1 and its number of digits, you obtain the same
>digits in the same order but rotated.
>As an example i'll give you this cyclic number:
>0588235294117647
>You can see that:
>0588235294117647 x 2 = 1176470588235294 (note the rotation)
>0588235294117647 x 3 = 1764705882352941
> ...
>0588235294117647 x 16 = 9411764705882352
>The fact is that doesn't exist such numbers for every numbers
>of digits. The smallest cyclic number has 6 digit. The questions
>are:
>1. Can you find it?
>2. If so, can you find a method (not brute-force) to find
>cyclic numbers of any number of digits?
Not for any number of digits (certainly not less than 6), but for
large numbers of digits.
>3. And if so, can you provide a math prove of it?
Assume we have a p+r digit number that we want to rotate r
digits by multiplying by m. The number can be written as
a x 10^r + b, where a < 10^(p+1) and b < 10^r
We must now solve the equation
m x (a x 10^r + b) = b x 10^p + a
<=>
a x (m x 10^r - 1) = b x (10^p - m)
Fixing m, p and r we get a single linear equation
a x v - b x w = 0, where v = m x 10^r - 1 and w = 10^p - m
with two unknowns a and b, which must be integers. This is a
diophantine equation and has the solutions
a = k x w / gcd(v,w)
b = k x v / gcd(v,w)
for any integer k. We must now find an r such that
a < 10^(p+1) and b < 10^r
according to our initial assumptions. This may or may not exist, but
is easy to test for any given choice of v,w.
We can see that since v = m x (10^r-1) and b < 10^r, gcd(v,w) must be
at least m for a solution to exist.
To find a six-digit cyclic number we have p+r = 6. For all r,m
combinations (m <= 6) we get (v,w) as shown in the table below
m \ r| 1 2 3 4 5
-----+-------------------------------------------------------
2 | (19,99998) (199,9998) (1999,998) (19999,98) (199999,8)
3 | (29,99997) (299,9997) (2999,997) (29999,97) (299999,7)
4 | (39,99996) (399,9996) (3999,996) (39999,96) (399999,6)
5 | (49,99995) (499,9995) (4999,995) (49999,95) (499999,5)
6 | (59,99994) (599,9994) (5999,994) (59999,94) (599999,4)
Of these gcd(19999,98) = 7, gcd(299,9997) = 13, gcd(299999,7) = 7,
gcd(39,99996) = 39, gcd(399,9996) = 21, gcd(49,99995) = 7 and
gcd(5999,994) = 7 are the only that satisfy gcd(v,w)>=m. From these we
get respectively
(m,r) = (2,5):
142857 x 2 = 285714 (k=1)
285714 x 2 = 571428 (k=2)
428571 x 2 = 857142 (k=3)
(m,r) = (3,2):
076923 x 3 = 230769 (k=1)
153846 x 3 = 461538 (k=2)
230769 x 3 = 692307 (k=3)
307692 x 3 = 923076 (k=4)
(m,r) = (3,5):
142857 x 3 = 428571 (k=1)
285714 x 3 = 857142 (k=2)
(m,r) = (4,1):
025641 x 4 = 102564 (k=1)
051282 x 4 = 205128 (k=2)
076923 x 4 = 307692 (k=3)
102564 x 4 = 410256 (k=4)
128205 x 4 = 512820 (k=5)
153846 x 4 = 615384 (k=6)
179487 x 4 = 717948 (k=7)
205128 x 4 = 820512 (k=8)
230769 x 4 = 923076 (k=9)
(m,r) = (4,2):
047619 x 4 = 190476 (k=1)
095238 x 4 = 380952 (k=2)
142857 x 4 = 571428 (k=3)
190476 x 4 = 761904 (k=4)
238095 x 4 = 952380 (k=5)
(m,r) = (5,1):
142857 x 5 = 714285 (k=1)
(m,r) = (6,3):
142857 x 6 = 857142 (k=1)
Since the number 142857 occurs for m = 2 up to 6:
142857 x 2 = 285714
142857 x 3 = 428571
142857 x 4 = 571428
142857 x 5 = 714285
142857 x 6 = 857142
it is a cyclic number.
The method above generalizes to arbitrary numbers of digits in the
number. You get a number of (m,r) pairs to test that is quadratic in
the number of digits. For those that yield gcd(v,w)>=m, you test a
number of k's that depend on the size of the gcd: the higher the cgd
the more cases you get. If there is no (v,w) such that gcd(v,w)>=m for
all m's between 2 and the number of digits, there is no cyclic
number. Even if there is, there may be no number common to the
solutions for all m's. To limit the cases you must test, try first the
m where the gcd's found are smallest. In the above example these would
be m = 2, 5 or 6 as these have 7 as the highest gcd(v,w). Then try the
solutions for this m with all the other m's. Note that any solution
must be less than (10^d)/d, where d is the number of digits. This
gives a quick test for potential solutions. For m=2 this immediately
narrows the search down to the single number 142857.
There is still some element of brute force in this method, but it is
certainly faster than trying all numbers.
Torben Mogensen (tor...@diku.dk)
Torben AEgidius Mogensen
tor...@diku.dk (Torben AEgidius Mogensen) writes:
>Carlos Bermejo <jc...@tid.es> writes:
>>Cyclic numbers are positive integers of a given number of
>>digits such that, when multiplying them by another integer
>>between 1 and its number of digits, you obtain the same
>>digits in the same order but rotated.
>>As an example i'll give you this cyclic number:
>>0588235294117647
>>You can see that:
>>0588235294117647 x 2 = 1176470588235294 (note the rotation)
>>0588235294117647 x 3 = 1764705882352941
>> ...
>>0588235294117647 x 16 = 9411764705882352
In my previous posting I showed a method and manually found the
6-digit cyclic number. I have now also found 18-digit, 22-digit,
28-digit, 46-digit, 58-digit and 60-digit cyclic numbers using he same
method (and a bit of computer assistance):
18:
052631578947368421
105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
526315789473684210
578947368421052631
631578947368421052
684210526315789473
736842105263157894
789473684210526315
842105263157894736
894736842105263157
947368421052631578
22:
0434782608695652173913
0869565217391304347826
1304347826086956521739
1739130434782608695652
2173913043478260869565
2608695652173913043478
3043478260869565217391
3478260869565217391304
3913043478260869565217
4347826086956521739130
4782608695652173913043
5217391304347826086956
5652173913043478260869
6086956521739130434782
6521739130434782608695
6956521739130434782608
7391304347826086956521
7826086956521739130434
8260869565217391304347
8695652173913043478260
9130434782608695652173
9565217391304347826086
28:
0344827586206896551724137931
0689655172413793103448275862
1034482758620689655172413793
1379310344827586206896551724
1724137931034482758620689655
2068965517241379310344827586
2413793103448275862068965517
2758620689655172413793103448
3103448275862068965517241379
3448275862068965517241379310
3793103448275862068965517241
4137931034482758620689655172
4482758620689655172413793103
4827586206896551724137931034
5172413793103448275862068965
5517241379310344827586206896
5862068965517241379310344827
6206896551724137931034482758
6551724137931034482758620689
6896551724137931034482758620
7241379310344827586206896551
7586206896551724137931034482
7931034482758620689655172413
8275862068965517241379310344
8620689655172413793103448275
8965517241379310344827586206
9310344827586206896551724137
9655172413793103448275862068
46:
0212765957446808510638297872340425531914893617
0425531914893617021276595744680851063829787234
0638297872340425531914893617021276595744680851
0851063829787234042553191489361702127659574468
1063829787234042553191489361702127659574468085
1276595744680851063829787234042553191489361702
1489361702127659574468085106382978723404255319
1702127659574468085106382978723404255319148936
1914893617021276595744680851063829787234042553
2127659574468085106382978723404255319148936170
2340425531914893617021276595744680851063829787
2553191489361702127659574468085106382978723404
2765957446808510638297872340425531914893617021
2978723404255319148936170212765957446808510638
3191489361702127659574468085106382978723404255
3404255319148936170212765957446808510638297872
3617021276595744680851063829787234042553191489
3829787234042553191489361702127659574468085106
4042553191489361702127659574468085106382978723
4255319148936170212765957446808510638297872340
4468085106382978723404255319148936170212765957
4680851063829787234042553191489361702127659574
4893617021276595744680851063829787234042553191
5106382978723404255319148936170212765957446808
5319148936170212765957446808510638297872340425
5531914893617021276595744680851063829787234042
5744680851063829787234042553191489361702127659
5957446808510638297872340425531914893617021276
6170212765957446808510638297872340425531914893
6382978723404255319148936170212765957446808510
6595744680851063829787234042553191489361702127
6808510638297872340425531914893617021276595744
7021276595744680851063829787234042553191489361
7234042553191489361702127659574468085106382978
7446808510638297872340425531914893617021276595
7659574468085106382978723404255319148936170212
7872340425531914893617021276595744680851063829
8085106382978723404255319148936170212765957446
8297872340425531914893617021276595744680851063
8510638297872340425531914893617021276595744680
8723404255319148936170212765957446808510638297
8936170212765957446808510638297872340425531914
9148936170212765957446808510638297872340425531
9361702127659574468085106382978723404255319148
9574468085106382978723404255319148936170212765
9787234042553191489361702127659574468085106382
58:
0169491525423728813559322033898305084745762711864406779661
0338983050847457627118644067796610169491525423728813559322
0508474576271186440677966101694915254237288135593220338983
0677966101694915254237288135593220338983050847457627118644
0847457627118644067796610169491525423728813559322033898305
1016949152542372881355932203389830508474576271186440677966
1186440677966101694915254237288135593220338983050847457627
1355932203389830508474576271186440677966101694915254237288
1525423728813559322033898305084745762711864406779661016949
1694915254237288135593220338983050847457627118644067796610
1864406779661016949152542372881355932203389830508474576271
2033898305084745762711864406779661016949152542372881355932
2203389830508474576271186440677966101694915254237288135593
2372881355932203389830508474576271186440677966101694915254
2542372881355932203389830508474576271186440677966101694915
2711864406779661016949152542372881355932203389830508474576
2881355932203389830508474576271186440677966101694915254237
3050847457627118644067796610169491525423728813559322033898
3220338983050847457627118644067796610169491525423728813559
3389830508474576271186440677966101694915254237288135593220
3559322033898305084745762711864406779661016949152542372881
3728813559322033898305084745762711864406779661016949152542
3898305084745762711864406779661016949152542372881355932203
4067796610169491525423728813559322033898305084745762711864
4237288135593220338983050847457627118644067796610169491525
4406779661016949152542372881355932203389830508474576271186
4576271186440677966101694915254237288135593220338983050847
4745762711864406779661016949152542372881355932203389830508
4915254237288135593220338983050847457627118644067796610169
5084745762711864406779661016949152542372881355932203389830
5254237288135593220338983050847457627118644067796610169491
5423728813559322033898305084745762711864406779661016949152
5593220338983050847457627118644067796610169491525423728813
5762711864406779661016949152542372881355932203389830508474
5932203389830508474576271186440677966101694915254237288135
6101694915254237288135593220338983050847457627118644067796
6271186440677966101694915254237288135593220338983050847457
6440677966101694915254237288135593220338983050847457627118
6610169491525423728813559322033898305084745762711864406779
6779661016949152542372881355932203389830508474576271186440
6949152542372881355932203389830508474576271186440677966101
7118644067796610169491525423728813559322033898305084745762
7288135593220338983050847457627118644067796610169491525423
7457627118644067796610169491525423728813559322033898305084
7627118644067796610169491525423728813559322033898305084745
7796610169491525423728813559322033898305084745762711864406
7966101694915254237288135593220338983050847457627118644067
8135593220338983050847457627118644067796610169491525423728
8305084745762711864406779661016949152542372881355932203389
8474576271186440677966101694915254237288135593220338983050
8644067796610169491525423728813559322033898305084745762711
8813559322033898305084745762711864406779661016949152542372
8983050847457627118644067796610169491525423728813559322033
9152542372881355932203389830508474576271186440677966101694
9322033898305084745762711864406779661016949152542372881355
9491525423728813559322033898305084745762711864406779661016
9661016949152542372881355932203389830508474576271186440677
9830508474576271186440677966101694915254237288135593220338
60:
016393442622950819672131147540983606557377049180327868852459
032786885245901639344262295081967213114754098360655737704918
049180327868852459016393442622950819672131147540983606557377
065573770491803278688524590163934426229508196721311475409836
081967213114754098360655737704918032786885245901639344262295
098360655737704918032786885245901639344262295081967213114754
114754098360655737704918032786885245901639344262295081967213
131147540983606557377049180327868852459016393442622950819672
147540983606557377049180327868852459016393442622950819672131
163934426229508196721311475409836065573770491803278688524590
180327868852459016393442622950819672131147540983606557377049
196721311475409836065573770491803278688524590163934426229508
213114754098360655737704918032786885245901639344262295081967
229508196721311475409836065573770491803278688524590163934426
245901639344262295081967213114754098360655737704918032786885
262295081967213114754098360655737704918032786885245901639344
278688524590163934426229508196721311475409836065573770491803
295081967213114754098360655737704918032786885245901639344262
311475409836065573770491803278688524590163934426229508196721
327868852459016393442622950819672131147540983606557377049180
344262295081967213114754098360655737704918032786885245901639
360655737704918032786885245901639344262295081967213114754098
377049180327868852459016393442622950819672131147540983606557
393442622950819672131147540983606557377049180327868852459016
409836065573770491803278688524590163934426229508196721311475
426229508196721311475409836065573770491803278688524590163934
442622950819672131147540983606557377049180327868852459016393
459016393442622950819672131147540983606557377049180327868852
475409836065573770491803278688524590163934426229508196721311
491803278688524590163934426229508196721311475409836065573770
508196721311475409836065573770491803278688524590163934426229
524590163934426229508196721311475409836065573770491803278688
540983606557377049180327868852459016393442622950819672131147
557377049180327868852459016393442622950819672131147540983606
573770491803278688524590163934426229508196721311475409836065
590163934426229508196721311475409836065573770491803278688524
606557377049180327868852459016393442622950819672131147540983
622950819672131147540983606557377049180327868852459016393442
639344262295081967213114754098360655737704918032786885245901
655737704918032786885245901639344262295081967213114754098360
672131147540983606557377049180327868852459016393442622950819
688524590163934426229508196721311475409836065573770491803278
704918032786885245901639344262295081967213114754098360655737
721311475409836065573770491803278688524590163934426229508196
737704918032786885245901639344262295081967213114754098360655
754098360655737704918032786885245901639344262295081967213114
770491803278688524590163934426229508196721311475409836065573
786885245901639344262295081967213114754098360655737704918032
803278688524590163934426229508196721311475409836065573770491
819672131147540983606557377049180327868852459016393442622950
836065573770491803278688524590163934426229508196721311475409
852459016393442622950819672131147540983606557377049180327868
868852459016393442622950819672131147540983606557377049180327
885245901639344262295081967213114754098360655737704918032786
901639344262295081967213114754098360655737704918032786885245
918032786885245901639344262295081967213114754098360655737704
934426229508196721311475409836065573770491803278688524590163
950819672131147540983606557377049180327868852459016393442622
967213114754098360655737704918032786885245901639344262295081
983606557377049180327868852459016393442622950819672131147540
In all of these cases the smallest gcd was d+1, where d is the number
of digits. By choosing the highest m where this is the only valid gcd,
I got the correct number immediately.
The program I used was written in Miranda (mainly because Miranda has
longnums). It is shown below. In addition to this program I did some
work by hand: First I called
[m | m<-[2..]; pcyclic m]
To obtain the numbers of digits that can have cyclic numbers. The
generated list was
[6,16,18,22,28,46,58,60
At which point even the longnums of Miranda overflowed.
For each of these numbers I would generate the list of (m,r,gcd)
tuples by calling glist, e.g. (glist 22), which gives
[(2,14,23),(3,2,23),(4,6,69),(5,7,23),(6,16,23),(7,1,69),(8,20,23),
(9,4,23),(10,1,99),(10,3,99),(10,5,99),(10,7,99),(10,9,99),
(10,10,99999999999),(10,11,99),(10,13,99),(10,15,99),(10,17,99),
(10,19,99),(10,21,9999999999999999999999),(11,19,23),(12,8,253),
(12,12,121),(13,10,69),(14,15,23),(15,9,23),(16,12,69),(17,5,23),
(18,18,23),(19,17,207),(20,13,23),(21,3,253),(21,9,121),(22,11,69)]
I then found that 20 is the highest m that has 23 as gcd. I then
called (abof 22 20 13) to get (43478260,8695652173913) which yields
the number 0434782608695652173913. Then I generated the list of
multiplies by [a*0434782608695652173913 | m<-[1..22]] which I then
laid out neatly using a text editor and then check that each number is
a rotation of the original. This I haven't done thoroughly, but my
random checking found no problems (making a program for testing
thoroughly is not hard to, I'm just lazy). If you don't believe me,
you are welcome to try and find errors.
Torben Mogensen (tor...@diku.dk)
===============8<------------------------------
gcd x 0 = x
gcd x y = gcd y (x mod y)
tento 0 = 1
tento n = 10*(tento (n-1)), n mod 2 = 1
tento n = square (tento (n div 2))
square x = x*x
vof m r = m*(tento r)-1
wof m0 m r = (tento (m0-r))-m
glist m0 = [(m,r,gcd (vof m r) (wof m0 m r)) |
m<-[2..m0]; r<-[1..m0-1];
gcd (vof m r) (wof m0 m r) >= m]
rlist m0 m = [r | r<-[1..m0-1]; gcd (vof m r) (wof m0 m r) >= m]
rcheck m0 m = #(rlist m0 m)~=0
forall f [] = True
forall f (a:l) = (f a) & (forall f l)
pcyclic m0 = forall (rcheck m0) [2..m0]
abof m0 m r = ((wof m0 m r) div (gcd (vof m r) (wof m0 m r)),
(vof m r) div (gcd (vof m r) (wof m0 m r)))
Troy Daniels
tor...@diku.dk (Torben AEgidius Mogensen) writes:
>
> tor...@diku.dk (Torben AEgidius Mogensen) writes:
>
> >Carlos Bermejo <jc...@tid.es> writes:
>
> >>Cyclic numbers are positive integers of a given number of
> >>digits such that, when multiplying them by another integer
> >>between 1 and its number of digits, you obtain the same
> >>digits in the same order but rotated.
>
> >>As an example i'll give you this cyclic number:
>
> >>0588235294117647
>
> >>You can see that:
>
> >>0588235294117647 x 2 = 1176470588235294 (note the rotation)
> >>0588235294117647 x 3 = 1764705882352941
> >> ...
> >>0588235294117647 x 16 = 9411764705882352
>
I believe that I have a much simpler method. Let p be prime, and not
2 or 5. The the decimal representation of 1/p will repeat after a
certain number of digits. Choose p such that 1/p repeats after p-1
digits, and call N(p) the digits that repeat. E.g.,
1/17 = .0588235294117647...
N(17) = 0588235294117647
N(p) for any of the primes p described above will be cyclic. (Note
that N(17) is the sample number).
Handwaving proof: 1/p, 10/p, 100/p will just shift the decimal point.
After subtracting the integer part, that sequence will map unto 1/p,
2/p, 3/p,..., (p-1)/p. (both sequences will have p-1 terms).
Troy Daniels
tdan...@fnal.gov