Jouer avec c = (a*b) mod (a+b);

Itérer.

 

 

J’ai envoyé récemment ce message aux listes MathFun et SeqFans:

 

______________________________________________

 

Date: lun. 07/07/2008 19:03

À: math-fun; seqfan@ext.jussieu.fr

Objet : Playing with c = (a*b) mod (a+b)

 

Hello MathFun & SeqFans,

 

  Start S = 2, 9,...

 

Next term is (2*9)mod(2+9)

               18 mod 11 = 7

  S = 2, 9, 7,...

 

Next term is (9*7)mod(9+7)

               63 mod 16 = 15

  S = 2, 9, 7, 15,...

 

Next term is (7*15)mod(7+15)

               105 mod 22 = 17

  S = 2, 9, 7, 15, 17,...

 

Next term is (15*17)mod(15+17)

               255 mod 32 = 31

  S = 2, 9, 7, 15, 17, 31,...

 

Next term is (17*31)mod(17+31)

               527 mod 48 = 47

 S = 2, 9, 7, 15, 17, 31, 47,...

 

Does this end in a loop?

If yes, is there another start

which doesn't?

 

Best,

É.

 

______________________________________________

 

 

Trois réponses intéressantes ont fusé :

 

[Chuck Seggelin] :

 

Hi Eric,

 

(...)

Looks like this sequence rapidly enters into repetition:

 

2, 9, 7, 15, 17, 31, 47, 53, 91, 71, 143, 95, 19, 95, 95, 95, ...

 

All remaining terms are 95. Many sequences of this variety (based on different starting terms) seem to "bottom out" fairly quickly. An interesting related seq might be if the first term is 2, what successive second terms give longer and longer non-repeating sequences?

 

2,3 goes 4 terms.

2,5 goes 6 terms.

2,9 goes 14 terms without repeating.

2,25 goes 21 terms which is the next record (25 is also the next odd square!)

2,27 goes 13.

2,29 goes 23 terms which is the new record.

The next record is at the next odd square 49, yielding 33 terms.

Then 99, yielding 36 terms.

...

 

So the first records are 3, 5, 9, 25, 29, 49, 99 (corresponding to 4, 6, 14, 21, 23, 33, 36).

 

Incidentally 2,61 gives the repeating loop with the most number of elements I've seen yet (six elements: 61, 59, 119, 79, 95, 23).

 

-- Chuck PlasteredDragon

 

 

[Jack Brennen] :

 

That one ends in a loop fairly quickly:

 

   2, 9, 7, 15, 17, 31, 47, 53, 91, 71, 143, 95, 19, 95, 95, 95, ...

 

Playing around with different starting pairs, it looks like all starting pairs may end up in a loop, or by going to the pair (0,0) which is either a loop or a singularity, depending on whether you take 0 mod 0 as being 0 or being undefined.  Furthermore, you can go an arbitrarily long time without looping.  Take for large a:

 

.., 6*a+6, 6*a, ...

 

The next term is 6*a-6, and progressively it goes down the ladder by steps of 6 until it terminates at ..., 18, 12, 6, 0, 0.

 

In a few minutes of searching, the longest sequence I could find which eventually loops without going to zero was the sequence starting with (29,574), which hits 855 at the 79th term and then stays at 855.

 

   Jack

 

Jack a envoyé cette suite à l’OEIS de Neil Sloane, c’est désormais la A137453.

 

 

[Maximilian Hasler] :

 

> Next term is (17*31)mod(17+31)

>               527 mod 48 = 47

>  S = 2, 9, 7, 15, 17, 31, 47,...

> 

> Does this end in a loop?

 

rather in a fixed point :

 

2, 9, 7, 15, 17, 31, 47, 53, 91, 71, 143, 95, 19, 95, 95, 95,

 

> If yes, is there another start which doesn't?

 

2,7 ends in a true loop:

 

EA([2,7])

[2, 7, 5, 11, 7, 5, 11, 7, 5, 11, 7, 5, 11, 7, 5, 11, 7, 5, 11,]

 

At a first glance, I can't find a starting value that would not end in a fixed point or a loop.

 

Many end in a loop consisting of {5,7,11} (in some order), sometimes reached after a long transition :

 

32, 51, 55, 49, 95, 47, 63, 101, 131, 7, 89, 47, 103, 41, 47, 79, 59,

107, 5, 87, 67, 131, 65, 87, 31, 101, 95, 187, 281, 131, 143, 101, 47,

11, 53, 7, 11, 5, 7, 11,...

 

But there are other loops possible, the first I found is

 

12, 99, 78, 111, 153, 87, 111, 153, 87, 111, 153, 87, 111, ...

 

There are longer loops :

 

14, 68, 50, 96, 128, 192, 256, 320, 128, 192, 256, 320, 128, 192, 256, 320

 

58, 79, 61, 59, 119, 79, 95, 23, 61, 59, 119, 79, 95, 23, 61, 59, 119, 79, 95, ...

 

32, 51, 55, 49, 95, 47, 63, 101, 131, 7, 89, 47, 103, 41, 47, 79, 59, 107, 5, 87, 67, 131, 65, 87, 31, 101, 95, 187, 281, 131...

 

One could imagine 2 seq :

 

A1 : square array T[i,j] = length of the cycle the seq. (b1,b2,(b1*b2) mod (b1+b2), (b2*b3) mod (b2+b3),...) will end in

 

A2 : square array T[i,j] = transition time before reaching the loop

 

One could also imagine a seq. where  b[k] +/* b[k-1] is replaced by sum/product of more (or all) terms.

 

As to the latter, will it always end in 0 ?

 

[3, 19, 13, 6, 18, 24, 52, 54, 54, 0 .....

[3, 17, 11, 3, 17, 0, 0, 0, 0, 0, 0.....

[3, 16, 10, 16, 30, 0, 0, 0, 0...

[3, 14, 8, 11, 24, 24, 0, 0, 0,.....

 

Then there is :

 

A3 : square array T[i,j] = transition time before reaching 0

 

which might be related to some gcd (euclid's algorithm) properties

 

  Maximilian

 

... et voici une quatrième réponse somptueuse de [Jacques Tramu] (citant par ailleurs Georges Brougnard) :

 

The following describes the behaviour of the sequence u(n) = (u(n-2)*u(n-1)) mod(u(n-1) + u(n-2)) for large integers:

 

10^1000    3.7125500000    4706    43      57

 

We take 100 random pairs of starters (u(0) =a, u(1)= b) < 10^1000 (1000 digits), and see that:

- the average sequence length (AVL)   is 1000* 3.71

- the  largest  sequence found has length 4706,

- 43% of sequences end in (0,0),

- 57 % end in a loop of fixed point.

 

The same for 10^p, 200 <= p <= 5000, each time 100 random pairs of starters.

 

One can see that the ratio R= AVL/p is close to 3.6 for all p in this sample.

 

10^200     3.7440500000    1009    50      50

10^400     3.7919000000    1960    43      57

10^600     3.6428000000    2863    52      48

10^800     3.6871250000    3787    47      53

10^1000    3.7125500000    4706    43      57

10^1200    3.5687666667    5463    54      46

10^1400    3.6217214286    6151    48      52

10^1600    3.5595187500    7125    52      48

10^1800    3.5865500000    7852    50      50

10^2000    3.5276800000    8875    55      45

10^2200    3.4119636364    9566    63      37

10^2400    3.5224416667    10469   55      45

10^2600    3.5431000000    11399   52      48

10^2800    3.6714142857    12160   42      58

10^3000    3.5366266667    12997   52      48

10^3200    3.4938656250    13873   56      44

10^3400    3.4834970588    14798   56      44

10^3600    3.6956305556    15528   39      61

10^3800    3.6228578947    16425   45      55

10^4000    3.4844000000    16984   55      45

10^4200    3.4705285714    18003   57      43

10^5000    3.5578060000    21355   49      51

 

Question : does the ratio R have a limit, have upper and lower bounds ?

 

My friend Georges Brougnard conjectured that lim(R)  = PI/2 * log(10) = 3.616892206, but offered no proof.

Regards,

JT

 

No divergent sequence was found,

No animal was harmed in the making of this experiment.

 

______________________________________________

 

 

Thanks to everyone !

(merci à tous)

 

Back to « light maths page »

Back to main page.

Back to Basics.