DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
tnp1.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.tnp1 Problème 3n + 1
4 #
5 # Cf. \htmlonly <a href="http://www.opimedia.be/3nP1/" target="_blank">
6 # <tt>http://www.opimedia.be/3nP1/</tt></a>\endhtmlonly
7 
8 ##\file
9 # Problème 3n + 1
10 #
11 # Cf. \htmlonly <a href="http://www.opimedia.be/3nP1/" target="_blank">
12 # <tt>http://www.opimedia.be/3nP1/</tt></a>\endhtmlonly
13 
14 # (c) Olivier Pirson --- DragonSoft
15 # http://www.opimedia.be/DS/
16 # Débuté le 14 juillet 2006
17 ####################################
18 from __future__ import print_function
19 
20 ## Date du dernier changement pour ce module
21 VERSION = 'tnp1 --- 2010 April 12'
22 
23 import numbers
24 
25 import DSPython
26 import DSPython.natural as natural
27 
28 
29 
30 # Fonction du problème original de (Lothar) Collatz :
31 #
32 # Pour tout n entier :
33 # L(n) := 2n /3 si n mod 3 = 0
34 # (4n - 1)/3 si n mod 3 = 1
35 # (4n + 1)/3 si n mod 3 = 2
36 #
37 # ==> L(-3) == -2
38 # L(-2) == -3
39 # L(-1) == -1
40 # L( 0) == 0
41 # L( 1) == 1
42 # L( 2) == 3
43 # L( 3) == 2
44 #
45 # Pour tout n entier :
46 # L*(n) := L^(n)(n)
47 
48 
49 # Fonctions liées au problème 3n+1 :
50 #
51 # Pour tout n entier :
52 # C(n) := n/2 si n pair
53 # 3n + 1 si n impair
54 #
55 # ==> C(-3) == -8
56 # C(-2) == -1
57 # C(-1) == -2
58 # C( 0) == 0
59 # C( 1) == 4
60 # C( 2) == 1
61 # C( 3) == 10
62 #
63 #
64 # n
65 # 3 ----- + 1
66 # 2^k
67 # F(n) := ------------- avec k = nombre de fois pour lequel n est divisible par 2
68 # 2^l l = nombre de fois pour lequel le numérateur est divisible par 2
69 #
70 # ==> F(-3) == -1
71 # F(-2) == -1
72 # F(-1) == -1
73 # F( 0) == 1
74 # F( 1) == 1
75 # F( 2) == 1
76 # F( 3) == 5
77 #
78 #
79 # T(n) := n/2 si n pair
80 # (3n + 1)/2 si n impair
81 #
82 # ==> T(-3) == -4
83 # T(-2) == -1
84 # T(-1) == -1
85 # T( 0) == 0
86 # T( 1) == 2
87 # T( 2) == 1
88 # T( 3) == 5
89 #
90 # T'(n) := L o T o L^(-1)
91 # T"(n) := L^(-1) o T o L
92 #
93 #
94 # U(n) := -1 si n == -1
95 # 0 si n == 0
96 # T^(k)(n) sinon
97 # avec k naturel tel que
98 # n, T(n), T^(2)(n), T^(3)(n), ... et T^(k-1)(n) soient de même parité
99 # et T^(k)(n) soit de parité contraire
100 #
101 # ==> U(-3) == -4
102 # U(-2) == -1
103 # U(-1) == -1
104 # U( 0) == 0
105 # U( 1) == 2
106 # U( 2) == 1
107 # U( 3) == 8
108 #
109 #
110 # Pour tout n naturel :
111 # C*(n) := C^(n)(n)
112 # T*(n) := T^(n)(n)
113 # T'*(n) := T'^(n)(n)
114 # T"*(n) := T"^(n)(n)
115 # F*(n) := F^(n)(n)
116 # U*(n) := U^(n)(n)
117 
118 
119 
120 # ###########
121 # Fonctions #
122 #############
123 # C()
124 ######
125 ## C(n)
126 def C(n):
127  """Renvoie la valeur de C(n) := n/2 si n pair
128  3n + 1 si n impair
129 
130  Pre: n: Integral
131 
132  Result: Integral
133 
134  O(n) = 1"""
135  assert isinstance(n, numbers.Integral), n
136 
137  return (n*3 + 1 if n&1
138  else n>>1)
139 
140 
141 ## C <sup>(k)</sup>(n)
142 def Ck(n, k):
143  """Renvoie la valeur de C^(k)(n)
144 
145  Pre: n: Integral
146  k: naturel
147 
148  Result: Integral
149 
150  O(n, k) = ..."""
151  assert isinstance(n, numbers.Integral), n
152  assert DSPython.natural_is(k), k
153 
154  if n == 0:
155  return 0
156  while k > 0:
157  if n&1 == 0: # étape(s) pair
158  s = natural.scan1(abs(n)) # |n| commence par s bits 0 (s >= 1)
159  if s < k: # s étapes paires
160  n >>= s
161  k -= s
162  else: # k étapes paires
163  return n >> k
164  else: # étape(s) impair
165  if n == 1:
166  return (1, 4, 2)[k%3]
167  elif n > 0:
168  s = natural.scan0(n) # n commence par s bits 1 (s >= 1)
169  if (s << 1) < k: # s doubles étapes impaires, paires
170  n = natural.pow3(s) * ((n >> s) + 1) - 1
171  # == (n' + 1) 3**s - 1 == n' 3**s + 3**s - 1 avec n' = n / (2**s)
172  k -= s << 1
173  elif k&1 == 0: # k doubles étapes impaires, paires
174  return natural.pow3(k>>1) * ((n >> (k>>1)) + 1) - 1
175  else: # k doubles étapes impaires, paires puis 1 étape impaire
176  return (natural.pow3(k>>1) * ((n >> (k>>1)) + 1) - 1) * 3 + 1
177  else:
178  if k > 1: # 1 étape impaire puis 1 étape paire
179  n = (n * 3 + 1) >> 1
180  k -= 2
181  else: # 1 étape impaire
182  n = n * 3 + 1
183  k -= 1
184  return n
185 
186 
187 ## C*(n)
188 def CS(n):
189  """Renvoie la valeur de C*(n) == C^(n)(n)
190 
191  Pre: n: naturel
192 
193  Result: Integral
194 
195  O(n) = ..."""
196  assert DSPython.natural_is(n), n
197 
198  return Ck(n, n)
199 
200 
201 ## C* <sup>(k)</sup>(n)
202 def CSk(n, k):
203  """Renvoie la valeur de C*^(k)(n)
204 
205  Pre: n: naturel
206  k: naturel
207 
208  Result: Integral
209 
210  O(n, k) = ..."""
211  assert DSPython.natural_is(n), n
212  assert DSPython.natural_is(k), k
213 
214  while k > 0:
215  if 0 <= n <= 2:
216  return ((0, 4, 4)[n] if k%2
217  else (0, 2, 2)[n])
218  n = CS(n)
219  k -= 1
220  return n
221 
222 
223 # F()
224 ######
225 ## F(n)
226 def F(n):
227  """_ n
228  3 ----- + 1
229  2^k
230  Renvoie la valeur de F(n) := -------------
231  2^l
232  avec k = nombre de fois pour lequel n est divisible par 2
233  l = nombre de fois pour lequel le numérateur est divisible par 2
234 
235  Pre: n: Integral
236 
237  Result: Integral
238 
239  O(n) = ..."""
240  assert isinstance(n, numbers.Integral), n
241 
242  if not (0 <= n <= 2):
243  if n&1 == 0: # n pair
244  n >>= natural.scan1(abs(n))
245  n = n * 3 + 1
246  return (n if n&1
247  else n >> natural.scan1(abs(n)))
248  else: # n == 0 ou 1 ou 2
249  return 1
250 
251 
252 ## F <sup>(k)</sup>(n)
253 def Fk(n, k):
254  """Renvoie la valeur de F^(k)(n)
255 
256  Pre: n: Integral
257  k: naturel
258 
259  Result: Integral
260 
261  O(n, k) = ..."""
262  assert isinstance(n, numbers.Integral), n
263  assert DSPython.natural_is(k), k
264 
265  while (k > 0) and (n != 1):
266  n = F(n)
267  k -= 1
268  return n
269 
270 
271 ## F*(n)
272 def FS(n):
273  """Renvoie la valeur de F*(n) == F^(n)(n)
274 
275  Pre: n: naturel
276 
277  Result: Integral
278 
279  O(n) = ..."""
280  assert DSPython.natural_is(n), n
281 
282  return Fk(n, n)
283 
284 
285 ## F* <sup>(k)</sup>(n)
286 def FSk(n, k):
287  """Renvoie la valeur de F*^(k)(n)
288 
289  Pre: n: naturel
290  k: naturel
291 
292  Result: Integral
293 
294  O(n, k) = ..."""
295  assert DSPython.natural_is(n), n
296  assert DSPython.natural_is(k), k
297 
298  while (k > 0) and (n != 1):
299  n = FS(n)
300  k -= 1
301  return n
302 
303 
304 # L()
305 ######
306 ## L(n)
307 def L(n):
308  """Renvoie la valeur L(n) := 2n /3 si n mod 3 = 0
309  (4n - 1)/3 si n mod 3 = 1
310  (4n + 1)/3 si n mod 3 = 2
311 
312  Pre: n: Integral
313 
314  Result: Integral
315 
316  O(n) = 1"""
317  assert isinstance(n, numbers.Integral), n
318 
319  n, m = divmod(n, 3)
320  return (n << 1 if m == 0
321  else (n << 2) + (1 if m == 1
322  else 3))
323 
324 
325 ## L <sup>(-1)</sup>(n)
326 def L_rec(n):
327  """Renvoie la valeur L^(-1)(n) = 3n /2 si n pair
328  (3n + 1)/4 si n mod 4 = 1
329  (3n - 1)/4 si n mod 4 = 3
330 
331  Pre: n: Integral
332 
333  Result: Integral
334 
335  O(n) = 1"""
336  assert isinstance(n, numbers.Integral), n
337 
338  return ((n >> 1) * 3 if n&1 == 0
339  else ((n * 3 - 1) if n&2
340  else (n * 3 + 1)) >> 2)
341 
342 
343 ## L <sup>(k)</sup>(n)
344 def Lk(n, k):
345  """Renvoie la valeur L^(k)(n)
346 
347  Pre: n: Integral
348  k: Integral
349 
350  Result: Integral
351 
352  O(n, k) = ..."""
353  assert isinstance(n, numbers.Integral), n
354  assert isinstance(k, numbers.Integral), k
355 
356  if k >= 0:
357  while k > 0:
358  n = L(n)
359  k -= 1
360  else:
361  while k < 0:
362  n = L_rec(n)
363  k += 1
364  return n
365 
366 
367 ## L*(n)
368 def LS(n):
369  """Renvoie la valeur de L*(n) == L^(n)(n)
370 
371  Pre: n: Integral
372 
373  Result: Integral
374 
375  O(n) = ..."""
376  assert isinstance(n, numbers.Integral), n
377 
378  return Lk(n, n)
379 
380 
381 ## L* <sup>(k)</sup>(n)
382 def LSk(n, k):
383  """Renvoie la valeur de L*^(k)(n)
384 
385  Pre: n: Integral
386  k: naturel
387 
388  Result: Integral
389 
390  O(n, k) = ..."""
391  assert isinstance(n, numbers.Integral), n
392  assert DSPython.natural_is(k), k
393 
394  while k > 0:
395  n = LS(n)
396  k -= 1
397  return n
398 
399 
400 # T()
401 ######
402 ## T(n)
403 def T(n):
404  """Renvoie la valeur de T(n) := n/2 si n pair
405  (3n + 1)/2 si n impair
406 
407  Pre: n: Integral
408 
409  Result: Integral
410 
411  O(n) = 1"""
412  assert isinstance(n, numbers.Integral), n
413 
414  return (n*3 + 1 if n&1
415  else n) >> 1
416 
417 
418 ## T <sup>(k)</sup>(n)
419 def Tk(n, k):
420  """Renvoie la valeur de T^(k)(n)
421 
422  Pre: n: Integral
423  k: naturel
424 
425  Result: Integral
426 
427  O(n, k) = ..."""
428  assert isinstance(n, numbers.Integral), n
429  assert DSPython.natural_is(k), k
430 
431  if n == 0:
432  return 0
433  while k > 0:
434  if n&1 == 0: # étape(s) pair
435  s = natural.scan1(abs(n)) # |n| commence par s bits 0 (s >= 1)
436  if s < k: # s étapes paires
437  n >>= s
438  k -= s
439  else: # k étapes paires
440  return n >> k
441  else: # étape(s) impair
442  if n == 1:
443  return (1, 2)[k%2]
444  elif n > 0:
445  s = natural.scan0(n) # n commence par s bits 1 (s >= 1)
446  if s < k: # s étapes impaires
447  n = natural.pow3(s) * ((n >> s) + 1) - 1
448  # == (n' + 1) 3**s - 1 == n' 3**s + 3**s - 1 avec n' = n / (2**s)
449  k -= s
450  else: # k étapes impaires
451  return natural.pow3(k) * ((n >> k) + 1) - 1
452  else: # 1 étape impaire
453  n = (n * 3 + 1) >> 1
454  k -= 1
455  return n
456 
457 
458 ## T*(n)
459 def TS(n):
460  """Renvoie la valeur de T*(n) == T^(n)(n)
461 
462  Pre: n: naturel
463 
464  Result: Integral
465 
466  O(n) = ..."""
467  assert DSPython.natural_is(n), n
468 
469  return Tk(n, n)
470 
471 
472 ## T* <sup>(k)</sup>(n)
473 def TSk(n, k):
474  """Renvoie la valeur de T*^(k)(n)
475 
476  Pre: n: naturel
477  k: naturel
478 
479  Result: Integral
480 
481  O(n, k) = ..."""
482  assert DSPython.natural_is(n), n
483  assert DSPython.natural_is(k), k
484 
485  if n != 0:
486  while (k > 0) and (n != 2):
487  n = TS(n)
488  k -= 1
489  return n
490 
491 
492 # T'()
493 #######
494 ## T'(n)
495 def TP(n):
496  """Renvoie la valeur de T'(n) := L o T o L^(-1) (n) = L( T( L^(-1)(n) ) )
497 
498  Pre: n: Integral
499 
500  Result: Integral
501 
502  O(n) = 1"""
503  assert isinstance(n, numbers.Integral), n
504 
505  return L(T(L_rec(n)))
506 
507 
508 ## T' <sup>(k)</sup>(n)
509 def TPk(n, k):
510  """Renvoie la valeur de T'^(k)(n)
511 
512  Pre: n: Integral
513  k: naturel
514 
515  Result: Integral
516 
517  O(n, k) = ..."""
518  assert isinstance(n, numbers.Integral), n
519  assert DSPython.natural_is(k), k
520 
521  return L(Tk(L_rec(n), k))
522 
523 
524 ## T'*(n)
525 def TPS(n):
526  """Renvoie la valeur de T'*(n) == T'^(n)(n)
527 
528  Pre: n: naturel
529 
530  Result: Integral
531 
532  O(n) = ..."""
533  assert DSPython.natural_is(n), n
534 
535  return TPk(n, n)
536 
537 
538 ## T'* <sup>(k)</sup>(n)
539 def TPSk(n, k):
540  """Renvoie la valeur de T'*^(k)(n)
541 
542  Pre: n: naturel
543  k: naturel
544 
545  Result: Integral
546 
547  O(n, k) = ..."""
548  assert DSPython.natural_is(n), n
549  assert DSPython.natural_is(k), k
550 
551  while k > 0:
552  n = TPS(n)
553  k -= 1
554  return n
555 
556 
557 # T"()
558 #######
559 ## T&quot;(n)
560 def TP2(n):
561  """Renvoie la valeur de T"(n) := L^(-1) o T o L (n) = L^(-1)( T( L(n) ) )
562 
563  Pre: n: Integral
564 
565  Result: Integral
566 
567  O(n) = 1""" #"
568  assert isinstance(n, numbers.Integral), n
569 
570  return L_rec(T(L(n)))
571 
572 
573 ## T&quot; <sup>(k)</sup>(n)
574 def TP2k(n, k):
575  """Renvoie la valeur de T"^(k)(n)
576 
577  Pre: n: Integral
578  k: naturel
579 
580  Result: Integral
581 
582  O(n, k) = ...""" #"
583  assert isinstance(n, numbers.Integral), n
584  assert DSPython.natural_is(k), k
585 
586  return L_rec(Tk(L(n), k))
587 
588 
589 ## T&quot;*(n)
590 def TP2S(n):
591  """Renvoie la valeur de T"*(n) == T"^(n)(n)
592 
593  Pre: n: naturel
594 
595  Result: Integral
596 
597  O(n) = ..."""
598  assert DSPython.natural_is(n), n
599 
600  return TP2k(n, n)
601 
602 
603 ## T&quot;* <sup>(k)</sup>(n)
604 def TP2Sk(n, k):
605  """Renvoie la valeur de T"*^(k)(n)
606 
607  Pre: n: naturel
608  k: naturel
609 
610  Result: Integral
611 
612  O(n, k) = ...""" #"
613  assert DSPython.natural_is(n), n
614  assert DSPython.natural_is(k), k
615 
616  while k > 0:
617  n = TP2S(n)
618  k -= 1
619  return n
620 
621 
622 # U()
623 ######
624 ## U(n)
625 def U(n):
626  """Renvoie la valeur de U(n) := -1 si n == -1
627  0 si n == 0
628  T^(k)(n) sinon
629  avec k naturel tel que
630  n, T(n), T^(2)(n), T^(3)(n)... et T^(k-1)(n) soient de même parité
631  et T^(k)(n) de parité contraire
632 
633  Pre: n: Integral
634 
635  Result: Integral
636 
637  O(n) = ..."""
638  assert isinstance(n, numbers.Integral), n
639 
640  if n&1 == 0: # 1 étape paire
641  return (n >> natural.scan1(abs(n)) if n != 0
642  else 0)
643  else: # 1 étape impaire
644  if n > 0:
645  s = natural.scan0(n) # n commence par s bits 1 (s >= 1)
646  return natural.pow3(s) * ((n >> s) + 1) - 1
647  else: # 1 étape impaire
648  if n != -1:
649  while n&1:
650  n = (n * 3 + 1) >> 1
651  return n
652 
653 
654 ## U <sup>(k)</sup>(n)
655 def Uk(n, k):
656  """Renvoie la valeur de U^(k)(n)
657 
658  Pre: n: Integral
659  k: naturel
660 
661  Result: Integral
662 
663  O(n, k) = ..."""
664  assert isinstance(n, numbers.Integral), n
665  assert DSPython.natural_is(k), k
666 
667  while (k > 0) and not(0 <= n <= 2):
668  n = U(n)
669  k -= 1
670  return (U(n) if k%2
671  else n)
672 
673 
674 ## U*(n)
675 def US(n):
676  """Renvoie la valeur de U*(n) == U^(n)(n)
677 
678  Pre: n: naturel
679 
680  Result: Integral
681 
682  O(n) = ..."""
683  assert DSPython.natural_is(n), n
684 
685  return Uk(n, n)
686 
687 
688 ## U* <sup>(k)</sup>(n)
689 def USk(n, k):
690  """Renvoie la valeur de U*^(k)(n)
691 
692  Pre: n: naturel
693  k: naturel
694 
695  Result: Integral
696 
697  O(n, k) = ..."""
698  assert DSPython.natural_is(n), n
699  assert DSPython.natural_is(k), k
700 
701  if n != 0:
702  while k > 0:
703  if 1 <= n <= 4:
704  return 2
705  n = US(n)
706  k -= 1
707  return n
708 
709 
710 
711 # ######\cond MAINTEST
712 # Main #
713 ########
714 if __name__ == '__main__':
715  def main_test():
716  """Test du module"""
717  import sys
718 
719  try:
720  if not 'profile' in dir():
721  import psyco
722  psyco.full()
723  except ImportError:
724  pass
725 
726  import DSPython.debug as debug
727 
728  debug.test_begin(VERSION, __debug__)
729 
730  # C()
731  print('C()...', end=''); sys.stdout.flush()
732  assert C(-5) == -14, C(-5)
733  assert C(-4) == -2, C(-4)
734  assert C(-3) == -8, C(-3)
735  assert C(-2) == -1, C(-2)
736  assert C(-1) == -2, C(-1)
737  assert C( 0) == 0, C( 0)
738  assert C( 1) == 4, C( 1)
739  assert C( 2) == 1, C( 2)
740  assert C( 3) == 10, C( 3)
741  assert C( 4) == 2, C( 4)
742  assert C( 5) == 16, C( 5)
743  print('ok'); sys.stdout.flush()
744 
745 
746  print('Ck()...', end=''); sys.stdout.flush()
747  assert Ck(-5, 1) == -14, Ck(-5, 1)
748  assert Ck(-4, 1) == -2, Ck(-4, 1)
749  assert Ck(-3, 1) == -8, Ck(-3, 1)
750  assert Ck(-2, 1) == -1, Ck(-2, 1)
751  assert Ck(-1, 1) == -2, Ck(-1, 1)
752  assert Ck( 0, 1) == 0, Ck( 0, 1)
753  assert Ck( 1, 1) == 4, Ck( 1, 1)
754  assert Ck( 2, 1) == 1, Ck( 2, 1)
755  assert Ck( 3, 1) == 10, Ck( 3, 1)
756  assert Ck( 4, 1) == 2, Ck( 4, 1)
757  assert Ck( 5, 1) == 16, Ck( 5, 1)
758  for n in range(-100, 100):
759  assert Ck(n, 0) == n, (n, Ck(n))
760  assert Ck(n, 1) == C(n), (n, Ck(n, 1), C(n))
761  assert Ck(n, 2) == C(C(n)), (n, Ck(n, 2), C(C(n)))
762  for k in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
763  assert Ck(n, k+1) == C(Ck(n, k)) == Ck(C(n), k), \
764  (n, k, Ck(n, k+1), C(Ck(n, k)), Ck(C(n), k))
765  if debug.assertspeed < debug.ASSERT_NORMAL:
766  print(debug.assertspeed_str(), end='')
767  print('ok'); sys.stdout.flush()
768 
769 
770  print('CS()...', end=''); sys.stdout.flush()
771  for n in range(100):
772  assert CS(n) == Ck(n, n), (n, CS(n), Ck(n, n))
773  print('ok'); sys.stdout.flush()
774 
775 
776  print('CSk()...', end=''); sys.stdout.flush()
777  for n in range(50):
778  assert CSk(n, 0) == n, (n, CSk(n, 0))
779  assert CSk(n, 1) == CS(n), (n, CSk(n, 1), CS(n))
780  assert CSk(n, 2) == CS(CS(n)), (n, CSk(n, 2), CS(CS(n)))
781  for k in range(20):
782  assert CSk(n, k+1) == CS(CSk(n, k)), (n, k, CSk(n, k+1), CS(CSk(n, k)))
783  print('ok'); sys.stdout.flush()
784 
785 
786  # F()
787  print('F()...', end=''); sys.stdout.flush()
788  assert F(-5) == -7, F(-5)
789  assert F(-4) == -1, F(-4)
790  assert F(-3) == -1, F(-3)
791  assert F(-2) == -1, F(-2)
792  assert F(-1) == -1, F(-1)
793  assert F( 0) == 1, F( 0)
794  assert F( 1) == 1, F( 1)
795  assert F( 2) == 1, F( 2)
796  assert F( 3) == 5, F( 3)
797  assert F( 4) == 1, F( 4)
798  assert F( 5) == 1, F( 5)
799  print('ok'); sys.stdout.flush()
800 
801 
802  print('Fk()...', end=''); sys.stdout.flush()
803  assert Fk(-5, 1) == -7, Fk(-5, 1)
804  assert Fk(-4, 1) == -1, Fk(-4, 1)
805  assert Fk(-3, 1) == -1, Fk(-3, 1)
806  assert Fk(-2, 1) == -1, Fk(-2, 1)
807  assert Fk(-1, 1) == -1, Fk(-1, 1)
808  assert Fk( 0, 1) == 1, Fk( 0, 1)
809  assert Fk( 1, 1) == 1, Fk( 1, 1)
810  assert Fk( 2, 1) == 1, Fk( 2, 1)
811  assert Fk( 3, 1) == 5, Fk( 3, 1)
812  assert Fk( 4, 1) == 1, Fk( 4, 1)
813  assert Fk( 5, 1) == 1, Fk( 5, 1)
814  for n in range(-50, 50):
815  assert Fk(n, 0) == n, (n, F(n))
816  assert Fk(n, 1) == F(n), (n, Fk(n, 1), F(n))
817  assert Fk(n, 2) == F(F(n)), (n, Fk(n, 2), F(F(n)))
818  for k in range(25):
819  assert Fk(n, k+1) == F(Fk(n, k)) == Fk(F(n), k), \
820  (n, k, Fk(n, k+1), F(Fk(n, k)), Fk(F(n), k))
821  print('ok'); sys.stdout.flush()
822 
823 
824  print('FS()...', end=''); sys.stdout.flush()
825  for n in range(100):
826  assert FS(n) == Fk(n, n), (n, FS(n), Fk(n, n))
827  print('ok'); sys.stdout.flush()
828 
829 
830  print('FSk()...', end=''); sys.stdout.flush()
831  for n in range(50):
832  assert FSk(n, 0) == n, (n, FSk(n, 0))
833  assert FSk(n, 1) == FS(n), (n, FSk(n, 1), FS(n))
834  assert FSk(n, 2) == FS(FS(n)), (n, FSk(n, 2), FS(FS(n)))
835  for k in range(20):
836  assert FSk(n, k+1) == FS(FSk(n, k)), (n, k, FSk(n, k+1), FS(FSk(n, k)))
837  print('ok'); sys.stdout.flush()
838 
839 
840  # L()
841  print('L()...', end=''); sys.stdout.flush()
842  assert L(-5) == -7, L(-5)
843  assert L(-4) == -5, L(-4)
844  assert L(-3) == -2, L(-3)
845  assert L(-2) == -3, L(-2)
846  assert L(-1) == -1, L(-1)
847  assert L( 0) == 0, L( 0)
848  assert L( 1) == 1, L( 1)
849  assert L( 2) == 3, L( 2)
850  assert L( 3) == 2, L( 3)
851  assert L( 4) == 5, L( 4)
852  assert L( 5) == 7, L( 5)
853  print('ok'); sys.stdout.flush()
854 
855 
856  print('L_rec()...', end=''); sys.stdout.flush()
857  assert L_rec(-5) == -4, L_rec(-5)
858  assert L_rec(-4) == -6, L_rec(-4)
859  assert L_rec(-3) == -2, L_rec(-3)
860  assert L_rec(-2) == -3, L_rec(-2)
861  assert L_rec(-1) == -1, L_rec(-1)
862  assert L_rec( 0) == 0, L_rec( 0)
863  assert L_rec( 1) == 1, L_rec( 1)
864  assert L_rec( 2) == 3, L_rec( 2)
865  assert L_rec( 3) == 2, L_rec( 3)
866  assert L_rec( 4) == 6, L_rec( 4)
867  assert L_rec( 5) == 4, L_rec( 5)
868  print('ok'); sys.stdout.flush()
869 
870 
871  print('Lk()...', end=''); sys.stdout.flush()
872  assert Lk(-5, 1) == -7, Lk(-5, 1)
873  assert Lk(-4, 1) == -5, Lk(-4, 1)
874  assert Lk(-3, 1) == -2, Lk(-3, 1)
875  assert Lk(-2, 1) == -3, Lk(-2, 1)
876  assert Lk(-1, 1) == -1, Lk(-1, 1)
877  assert Lk( 0, 1) == 0, Lk( 0, 1)
878  assert Lk( 1, 1) == 1, Lk( 1, 1)
879  assert Lk( 2, 1) == 3, Lk( 2, 1)
880  assert Lk( 3, 1) == 2, Lk( 3, 1)
881  assert Lk( 4, 1) == 5, Lk( 4, 1)
882  assert Lk( 5, 1) == 7, Lk( 5, 1)
883  for n in range(-50, 50):
884  assert Lk(n, 0) == n, (n, L(n))
885  assert Lk(n, 1) == L(n), (n, Lk(n, 1), L(n))
886  assert Lk(n, 2) == L(L(n)), (n, Lk(n, 2), L(L(n)))
887  assert Lk(n, -1) == L_rec(n), (n, Lk(n, -1), L_rec(n))
888  assert Lk(n, -2) == L_rec(L_rec(n)), (n, Lk(n, -2), L_rec(L_rec(n)))
889  for k in range(25):
890  assert Lk(n, k+1) == L(Lk(n, k)) == Lk(L(n), k), \
891  (n, k, Lk(n, k+1), L(Lk(n, k)), Lk(L(n), k))
892  assert Lk(n, -(k+1)) == L_rec(Lk(n, -k)) == Lk(L_rec(n), -k), \
893  (n, -k, Lk(n, -(k+1)), L_rec(Lk(n, -k)), Lk(L_rec(n), -k))
894  print('ok'); sys.stdout.flush()
895 
896 
897  print('LS()...', end=''); sys.stdout.flush()
898  for n in range(-100, 100):
899  assert LS(n) == Lk(n, n), (n, LS(n), Lk(n, n))
900  print('ok'); sys.stdout.flush()
901 
902 
903  print('LSk()...', end=''); sys.stdout.flush()
904  for n in range(30 if debug.assertspeed >= debug.ASSERT_NORMAL else 10):
905  assert LSk(n, 0) == n, (n, LSk(n, 0))
906  assert LSk(n, 1) == LS(n), (n, LSk(n, 1), LS(n))
907  assert LSk(n, 2) == LS(LS(n)), (n, LSk(n, 2), LS(LS(n)))
908  for k in range(10):
909  if ((n == 8)
910  or (n >= 10)
911  and ((k == 3) or ((n >= 17) and (k == 2)))):
912  break
913  assert LSk(n, k+1) == LS(LSk(n, k)), (n, k, LSk(n, k+1), LS(LSk(n, k)))
914  if debug.assertspeed < debug.ASSERT_NORMAL:
915  print(debug.assertspeed_str(), end='')
916  print('ok'); sys.stdout.flush()
917 
918 
919  # T()
920  print('T()...', end=''); sys.stdout.flush()
921  assert T(-5) == -7, T(-5)
922  assert T(-4) == -2, T(-4)
923  assert T(-3) == -4, T(-3)
924  assert T(-2) == -1, T(-2)
925  assert T(-1) == -1, T(-1)
926  assert T( 0) == 0, T( 0)
927  assert T( 1) == 2, T( 1)
928  assert T( 2) == 1, T( 2)
929  assert T( 3) == 5, T( 3)
930  assert T( 4) == 2, T( 4)
931  assert T( 5) == 8, T( 5)
932  for n in range(-100, 100):
933  if n&1 == 0: # n pair
934  assert T(n) == C(n), (n, T(n), C(n))
935  else: # n impair
936  assert T(n) == Ck(n, 2), (n, T(n), Ck(n, 2))
937  print('ok'); sys.stdout.flush()
938 
939 
940  print('Tk()...', end=''); sys.stdout.flush()
941  assert Tk(-5, 1) == -7, Tk(-5, 1)
942  assert Tk(-4, 1) == -2, Tk(-4, 1)
943  assert Tk(-3, 1) == -4, Tk(-3, 1)
944  assert Tk(-2, 1) == -1, Tk(-2, 1)
945  assert Tk(-1, 1) == -1, Tk(-1, 1)
946  assert Tk( 0, 1) == 0, Tk( 0, 1)
947  assert Tk( 1, 1) == 2, Tk( 1, 1)
948  assert Tk( 2, 1) == 1, Tk( 2, 1)
949  assert Tk( 3, 1) == 5, Tk( 3, 1)
950  assert Tk( 4, 1) == 2, Tk( 4, 1)
951  assert Tk( 5, 1) == 8, Tk( 5, 1)
952  for n in range(-100, 100):
953  assert Tk(n, 0) == n, (n, Tk(n, 0))
954  assert Tk(n, 1) == T(n), (n, Tk(n, 1), T(n))
955  assert Tk(n, 2) == T(T(n)), (n, Tk(n, 2), T(T(n)))
956  for k in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
957  assert Tk(n, k+1) == T(Tk(n, k)) == Tk(T(n), k), \
958  (n, k, Tk(n, k+1), T(Tk(n, k)), Tk(T(n), k))
959  if debug.assertspeed < debug.ASSERT_NORMAL:
960  print(debug.assertspeed_str(), end='')
961  print('ok'); sys.stdout.flush()
962 
963 
964  print('TS()...', end=''); sys.stdout.flush()
965  for n in range(100):
966  assert TS(n) == Tk(n, n), (n, TS(n), Tk(n, n))
967  print('ok'); sys.stdout.flush()
968 
969 
970  print('TSk()...', end=''); sys.stdout.flush()
971  for n in range(50):
972  assert TSk(n, 0) == n, (n, TSk(n, 0))
973  assert TSk(n, 1) == TS(n), (n, TSk(n, 1), TS(n))
974  assert TSk(n, 2) == TS(TS(n)), (n, TSk(n, 2), TS(TS(n)))
975  for k in range(20):
976  assert TSk(n, k+1) == TS(TSk(n, k)), (n, k, TSk(n, k+1), TS(TSk(n, k)))
977  print('ok'); sys.stdout.flush()
978 
979 
980  # T'()
981  print('TP()...', end=''); sys.stdout.flush()
982  assert TP(-5) == -3, TP(-5)
983  assert TP(-4) == -2, TP(-4)
984  assert TP(-3) == -1, TP(-3)
985  assert TP(-2) == -5, TP(-2)
986  assert TP(-1) == -1, TP(-1)
987  assert TP( 0) == 0, TP( 0)
988  assert TP( 1) == 3, TP( 1)
989  assert TP( 2) == 7, TP( 2)
990  assert TP( 3) == 1, TP( 3)
991  assert TP( 4) == 2, TP( 4)
992  assert TP( 5) == 3, TP( 5)
993  for n in range(-100, 100):
994  assert TP(n) == L(T(L_rec(n))), (n, TP(n), L(T(L_rec(n))))
995  print('ok'); sys.stdout.flush()
996 
997 
998  print('TPk()...', end=''); sys.stdout.flush()
999  assert TPk(-5, 1) == -3, TPk(-5, 1)
1000  assert TPk(-4, 1) == -2, TPk(-4, 1)
1001  assert TPk(-3, 1) == -1, TPk(-3, 1)
1002  assert TPk(-2, 1) == -5, TPk(-2, 1)
1003  assert TPk(-1, 1) == -1, TPk(-1, 1)
1004  assert TPk( 0, 1) == 0, TPk( 0, 1)
1005  assert TPk( 1, 1) == 3, TPk( 1, 1)
1006  assert TPk( 2, 1) == 7, TPk( 2, 1)
1007  assert TPk( 3, 1) == 1, TPk( 3, 1)
1008  assert TPk( 4, 1) == 2, TPk( 4, 1)
1009  assert TPk( 5, 1) == 3, TPk( 5, 1)
1010  for n in range(-100, 100):
1011  assert TPk(n, 0) == n, (n, TPk(n, 0))
1012  assert TPk(n, 1) == TP(n), (n, TPk(n, 1), TP(n))
1013  assert TPk(n, 2) == TP(TP(n)), (n, TPk(n, 2), TP(TP(n)))
1014  for k in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 25):
1015  assert TPk(n, k+1) == TP(TPk(n, k)) == TPk(TP(n), k), \
1016  (n, k, TPk(n, k+1), TP(TPk(n, k)), TPk(TP(n), k))
1017  if debug.assertspeed < debug.ASSERT_NORMAL:
1018  print(debug.assertspeed_str(), end='')
1019  print('ok'); sys.stdout.flush()
1020 
1021 
1022  print('TPS()...', end=''); sys.stdout.flush()
1023  for n in range(100):
1024  assert TPS(n) == TPk(n, n), (n, TPS(n), TPk(n, n))
1025  print('ok'); sys.stdout.flush()
1026 
1027 
1028  print('TPSk()...', end=''); sys.stdout.flush()
1029  for n in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 25):
1030  assert TPSk(n, 0) == n, (n, TPSk(n, 0))
1031  assert TPSk(n, 1) == TPS(n), (n, TPSk(n, 1), TPS(n))
1032  assert TPSk(n, 2) == TPS(TPS(n)), (n, TPSk(n, 2), TPS(TPS(n)))
1033  for k in range(20):
1034  assert TPSk(n, k+1) == TPS(TPSk(n, k)), (n, k, TPSk(n, k+1), TPS(TPSk(n, k)))
1035  if debug.assertspeed < debug.ASSERT_NORMAL:
1036  print(debug.assertspeed_str(), end='')
1037  print('ok'); sys.stdout.flush()
1038 
1039 
1040  # T"()
1041  print('TP2()...', end=''); sys.stdout.flush()
1042  assert TP2(-5) == -15, TP2(-5)
1043  assert TP2(-4) == -5, TP2(-4)
1044  assert TP2(-3) == -1, TP2(-3)
1045  assert TP2(-2) == -6, TP2(-2)
1046  assert TP2(-1) == -1, TP2(-1)
1047  assert TP2( 0) == 0, TP2( 0)
1048  assert TP2( 1) == 3, TP2( 1)
1049  assert TP2( 2) == 4, TP2( 2)
1050  assert TP2( 3) == 1, TP2( 3)
1051  assert TP2( 4) == 12, TP2( 4)
1052  assert TP2( 5) == 8, TP2( 5)
1053  for n in range(-100, 100):
1054  assert TP2(n) == L_rec(T(L(n))), (n, TP2(n), L_rec(T(L(n))))
1055  print('ok'); sys.stdout.flush()
1056 
1057 
1058  print('TP2k()...', end=''); sys.stdout.flush()
1059  assert TP2k(-5, 1) == -15, TP2k(-5, 1)
1060  assert TP2k(-4, 1) == -5, TP2k(-4, 1)
1061  assert TP2k(-3, 1) == -1, TP2k(-3, 1)
1062  assert TP2k(-2, 1) == -6, TP2k(-2, 1)
1063  assert TP2k(-1, 1) == -1, TP2k(-1, 1)
1064  assert TP2k( 0, 1) == 0, TP2k( 0, 1)
1065  assert TP2k( 1, 1) == 3, TP2k( 1, 1)
1066  assert TP2k( 2, 1) == 4, TP2k( 2, 1)
1067  assert TP2k( 3, 1) == 1, TP2k( 3, 1)
1068  assert TP2k( 4, 1) == 12, TP2k( 4, 1)
1069  assert TP2k( 5, 1) == 8, TP2k( 5, 1)
1070  for n in range(-100, 100):
1071  assert TP2k(n, 0) == n, (n, TP2k(n, 0))
1072  assert TP2k(n, 1) == TP2(n), (n, TP2k(n, 1), TP2(n))
1073  assert TP2k(n, 2) == TP2(TP2(n)), (n, TP2k(n, 2), TP2(TP2(n)))
1074  for k in range(50):
1075  assert TP2k(n, k+1) == TP2(TP2k(n, k)) == TP2k(TP2(n), k), \
1076  (n, k, TP2k(n, k+1), TP2(TP2k(n, k)), TP2k(TP2(n), k))
1077  print('ok'); sys.stdout.flush()
1078 
1079 
1080  print('TP2S()...', end=''); sys.stdout.flush()
1081  for n in range(100):
1082  assert TP2S(n) == TP2k(n, n), (n, TP2S(n), TP2k(n, n))
1083  print('ok'); sys.stdout.flush()
1084 
1085 
1086  print('TP2Sk()...', end=''); sys.stdout.flush()
1087  for n in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 25):
1088  assert TP2Sk(n, 0) == n, (n, TP2Sk(n, 0))
1089  assert TP2Sk(n, 1) == TP2S(n), (n, TP2Sk(n, 1), TP2S(n))
1090  assert TP2Sk(n, 2) == TP2S(TP2S(n)), (n, TP2Sk(n, 2), TP2S(TP2S(n)))
1091  for k in range(20):
1092  assert TP2Sk(n, k+1) == TP2S(TP2Sk(n, k)), (n, k, TP2Sk(n, k+1), TP2S(TP2Sk(n, k)))
1093  if debug.assertspeed < debug.ASSERT_NORMAL:
1094  print(debug.assertspeed_str(), end='')
1095  print('ok'); sys.stdout.flush()
1096 
1097  # U()
1098  print('U()...', end=''); sys.stdout.flush()
1099  assert U(-5) == -10, U(-5)
1100  assert U(-4) == -1, U(-4)
1101  assert U(-3) == -4, U(-3)
1102  assert U(-2) == -1, U(-2)
1103  assert U(-1) == -1, U(-1)
1104  assert U( 0) == 0, U( 0)
1105  assert U( 1) == 2, U( 1)
1106  assert U( 2) == 1, U( 2)
1107  assert U( 3) == 8, U( 3)
1108  assert U( 4) == 1, U( 4)
1109  assert U( 5) == 8, U( 5)
1110  for n in range(-100, -1):
1111  t = T(n)
1112  while t & 1 == n & 1: # t et n de même parité
1113  t = T(t)
1114  assert U(n) == t, (n, U(n), t)
1115  for n in range(1, 100):
1116  t = T(n)
1117  while t & 1 == n & 1: # t et n de même parité
1118  t = T(t)
1119  assert U(n) == t, (n, U(n), t)
1120  print('ok'); sys.stdout.flush()
1121 
1122 
1123  print('Uk()...', end=''); sys.stdout.flush()
1124  assert Uk(-5, 1) == -10, Uk(-5, 1)
1125  assert Uk(-4, 1) == -1, Uk(-4, 1)
1126  assert Uk(-3, 1) == -4, Uk(-3, 1)
1127  assert Uk(-2, 1) == -1, Uk(-2, 1)
1128  assert Uk(-1, 1) == -1, Uk(-1, 1)
1129  assert Uk( 0, 1) == 0, Uk( 0, 1)
1130  assert Uk( 1, 1) == 2, Uk( 1, 1)
1131  assert Uk( 2, 1) == 1, Uk( 2, 1)
1132  assert Uk( 3, 1) == 8, Uk( 3, 1)
1133  assert Uk( 4, 1) == 1, Uk( 4, 1)
1134  assert Uk( 5, 1) == 8, Uk( 5, 1)
1135  for n in range(-50, 50):
1136  assert Uk(n, 0) == n, (n, U(n))
1137  assert Uk(n, 1) == U(n), (n, Uk(n, 1), U(n))
1138  assert Uk(n, 2) == U(U(n)), (n, Uk(n, 2), U(U(n)))
1139  for k in range(25):
1140  assert Uk(n, k+1) == U(Uk(n, k)) == Uk(U(n), k), \
1141  (n, k, Uk(n, k+1), U(Uk(n, k)), Uk(U(n), k))
1142  print('ok'); sys.stdout.flush()
1143 
1144 
1145  print('US()...', end=''); sys.stdout.flush()
1146  for n in range(100):
1147  assert US(n) == Uk(n, n), (n, US(n), Uk(n, n))
1148  print('ok'); sys.stdout.flush()
1149 
1150 
1151  print('USk()...', end=''); sys.stdout.flush()
1152  for n in range(50):
1153  assert USk(n, 0) == n, (n, USk(n, 0))
1154  assert USk(n, 1) == US(n), (n, USk(n, 1), US(n))
1155  assert USk(n, 2) == US(US(n)), (n, USk(n, 2), US(US(n)))
1156  for k in range(20):
1157  assert USk(n, k+1) == US(USk(n, k)), (n, k, USk(n, k+1), US(USk(n, k)))
1158  print('ok'); sys.stdout.flush()
1159  debug.test_end()
1160 
1161  main_test()
1162 ##\endcond MAINTEST