DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
nat32.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.nat32 Naturels sur 32 bits
4 
5 ##\file
6 # Naturels sur 32 bits
7 
8 # (c) Olivier Pirson --- DragonSoft
9 # http://www.opimedia.be/DS/
10 # Débuté le 30 juillet 2006
11 ####################################
12 from __future__ import division
13 from __future__ import print_function
14 
15 ## Date du dernier changement pour ce module
16 VERSION = 'nat32 --- 2010 March 16'
17 
18 import array, bisect, fractions, math
19 
20 import DSPython
21 import DSPython.bit32 as bit32
22 
23 
24 
25 # ############
26 # Constantes #
27 ##############
28 ## n!, factoriels tenant sur 32 bits
29 FACTORIAL_TUPLE = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600)
30 
31 
32 ## Nombres de Fibonacci F<sub>n</sub> tenant sur 32 bits
33 FIBONACCI_TUPLE = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
34  1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
35  196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887,
36  9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
37  267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073)
38 
39 
40 ## Restes modulo 2 qui sont premiers avec 2 (2 == primorielle(1))
41 MODS_PRIMORIAL_1_TUPLE = (1)
42 
43 
44 ## Restes modulo 6 qui sont premiers avec 6 (6 == primorielle(2) == 2 * 3)
45 MODS_PRIMORIAL_2_TUPLE = (1, 5)
46 
47 
48 ## Restes modulo 30 qui sont premiers avec 30 (30 == primorielle(3) == 2 * 3 * 5)
49 MODS_PRIMORIAL_3_TUPLE = (1, 7, 11, 13, 17, 19, 23, 29)
50 
51 
52 ## Restes modulo 210 qui sont premiers avec 210 (210 == primorielle(4) == 2 * 3 * 5 * 7)
53 MODS_PRIMORIAL_4_TUPLE = (1, 11, 13, 17, 19, 23, 29, 31,
54  37, 41, 43, 47, 53, 59, 61, 67,
55  71, 73, 79, 83, 89, 97, 101, 103,
56  107, 109, 113, 121, 127, 131, 137, 139,
57  143, 149, 151, 157, 163, 167, 169, 173,
58  179, 181, 187, 191, 193, 197, 199, 209)
59 
60 
61 ## Différence des restes modulo 210 qui sont premiers avec 210
62 MODS_PRIMORIAL_4_DIFF_TUPLE = (10, 2, 4, 2, 4, 6, 2, 6,
63  4, 2, 4, 6, 6, 2, 6, 4,
64  2, 6, 4, 6, 8, 4, 2, 4,
65  2, 4, 8, 6, 4, 6, 2, 4,
66  6, 2, 6, 6, 4, 2, 4, 6,
67  2, 6, 4, 2, 4, 2, 10, 2)
68 
69 
70 ## Restes modulo primorielle(n) pour n allant de 1 à 4
71 MODS_PRIMORIALS_TUPLE = (MODS_PRIMORIAL_1_TUPLE, MODS_PRIMORIAL_2_TUPLE, MODS_PRIMORIAL_3_TUPLE,
72  MODS_PRIMORIAL_4_TUPLE)
73 
74 
75 
76 
77 ## 3<sup>k</sup>, puissances de 3 tenant sur 32 bits
78 POW3_TUPLE = (1, 3, 9, 27, 81,
79  243, 729, 2187, 6561, 19683,
80  59049, 177147, 531441, 1594323, 4782969,
81  14348907, 43046721, 129140163, 387420489, 1162261467,
82  3486784401)
83 
84 
85 ## Nombres premiers tenant sur 16 bits
86 PRIME_16_ARRAY = array.array('H',
87  (2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
88  31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
89  73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
90  127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
91  179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
92  233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
93  283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
94  353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
95  419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
96  467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
97  547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
98  607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
99  661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
100  739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
101  811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
102  877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
103  947 , 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
104  1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
105  1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
106  1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
107  1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
108  1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
109  1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
110  1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
111  1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
112  1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
113  1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
114  1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
115  1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
116  1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
117  1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
118  2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
119  2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
120  2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
121  2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
122  2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
123  2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
124  2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
125  2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
126  2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
127  2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
128  2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
129  2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
130  3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
131  3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
132  3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
133  3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
134  3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
135  3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
136  3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
137  3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
138  3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
139  3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
140  3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
141  3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
142  4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
143  4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
144  4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
145  4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
146  4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
147  4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
148  4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
149  4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
150  4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
151  4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831,
152  4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
153  4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003,
154  5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
155  5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
156  5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279,
157  5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387,
158  5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
159  5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
160  5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639,
161  5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693,
162  5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
163  5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
164  5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
165  5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
166  6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
167  6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221,
168  6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
169  6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367,
170  6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
171  6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
172  6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
173  6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761,
174  6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
175  6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917,
176  6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
177  7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
178  7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
179  7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297,
180  7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411,
181  7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499,
182  7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
183  7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643,
184  7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723,
185  7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
186  7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
187  7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017,
188  8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
189  8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219,
190  8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
191  8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387,
192  8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501,
193  8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597,
194  8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
195  8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741,
196  8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
197  8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929,
198  8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
199  9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109,
200  9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199,
201  9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283,
202  9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
203  9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439,
204  9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533,
205  9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631,
206  9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
207  9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811,
208  9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887,
209  9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007,
210  10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
211  10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177,
212  10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271,
213  10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343,
214  10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
215  10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567,
216  10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657,
217  10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739,
218  10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
219  10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949,
220  10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059,
221  11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149,
222  11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
223  11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329,
224  11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443,
225  11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527,
226  11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
227  11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777,
228  11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833,
229  11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
230  11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
231  12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109,
232  12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211,
233  12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289,
234  12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
235  12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487,
236  12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553,
237  12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641,
238  12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
239  12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829,
240  12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
241  12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007,
242  13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
243  13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187,
244  13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309,
245  13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
246  13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
247  13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619,
248  13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697,
249  13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781,
250  13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
251  13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
252  13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081,
253  14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197,
254  14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
255  14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419,
256  14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519,
257  14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593,
258  14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
259  14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767,
260  14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851,
261  14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947,
262  14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
263  15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149,
264  15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259,
265  15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319,
266  15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
267  15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
268  15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607,
269  15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679,
270  15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
271  15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881,
272  15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971,
273  15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
274  16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
275  16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267,
276  16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381,
277  16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481,
278  16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
279  16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691,
280  16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811,
281  16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903,
282  16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
283  17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093,
284  17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
285  17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317,
286  17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
287  17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477,
288  17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573,
289  17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669,
290  17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
291  17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891,
292  17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971,
293  17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059,
294  18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143,
295  18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233,
296  18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313,
297  18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427,
298  18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517,
299  18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637,
300  18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749,
301  18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899,
302  18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009,
303  19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121,
304  19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219,
305  19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319,
306  19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423,
307  19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477,
308  19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571,
309  19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699,
310  19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793,
311  19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891,
312  19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991,
313  19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071,
314  20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149,
315  20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261,
316  20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357,
317  20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443,
318  20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551,
319  20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693,
320  20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771,
321  20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897,
322  20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983,
323  21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067,
324  21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169,
325  21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277,
326  21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383,
327  21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491,
328  21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563,
329  21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647,
330  21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751,
331  21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841,
332  21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943,
333  21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039,
334  22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123,
335  22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229,
336  22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307,
337  22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441,
338  22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543,
339  22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643,
340  22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727,
341  22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817,
342  22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943,
343  22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029,
344  23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099,
345  23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203,
346  23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321,
347  23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447,
348  23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561,
349  23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629,
350  23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743,
351  23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827,
352  23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909,
353  23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007,
354  24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091,
355  24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169,
356  24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281,
357  24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413,
358  24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517,
359  24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659,
360  24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767,
361  24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877,
362  24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977,
363  24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097,
364  25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183,
365  25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303,
366  25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391,
367  25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471,
368  25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603,
369  25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693,
370  25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799,
371  25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913,
372  25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999,
373  26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111,
374  26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203,
375  26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297,
376  26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399,
377  26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497,
378  26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633,
379  26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711,
380  26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801,
381  26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891,
382  26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987,
383  26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077,
384  27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211,
385  27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329,
386  27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449,
387  27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551,
388  27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691,
389  27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767,
390  27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827,
391  27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947,
392  27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051,
393  28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151,
394  28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283,
395  28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403,
396  28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499,
397  28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579,
398  28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649,
399  28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729,
400  28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837,
401  28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933,
402  28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059,
403  29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167,
404  29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251,
405  29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363,
406  29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443,
407  29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573,
408  29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671,
409  29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819,
410  29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921,
411  29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059,
412  30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137,
413  30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241,
414  30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341,
415  30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469,
416  30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559,
417  30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689,
418  30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803,
419  30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871,
420  30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983,
421  31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091,
422  31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183,
423  31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259,
424  31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357,
425  31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511,
426  31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601,
427  31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721,
428  31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817,
429  31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973,
430  31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059, 32063,
431  32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159,
432  32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257,
433  32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353,
434  32359, 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423,
435  32429, 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531,
436  32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587, 32603, 32609,
437  32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717,
438  32719, 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831,
439  32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933, 32939,
440  32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999, 33013, 33023,
441  33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091, 33107, 33113,
442  33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203, 33211,
443  33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343,
444  33347, 33349, 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427,
445  33457, 33461, 33469, 33479, 33487, 33493, 33503, 33521, 33529, 33533,
446  33547, 33563, 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613,
447  33617, 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703, 33713,
448  33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773, 33791, 33797,
449  33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871, 33889, 33893,
450  33911, 33923, 33931, 33937, 33941, 33961, 33967, 33997, 34019, 34031,
451  34033, 34039, 34057, 34061, 34123, 34127, 34129, 34141, 34147, 34157,
452  34159, 34171, 34183, 34211, 34213, 34217, 34231, 34253, 34259, 34261,
453  34267, 34273, 34283, 34297, 34301, 34303, 34313, 34319, 34327, 34337,
454  34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429, 34439, 34457,
455  34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537,
456  34543, 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649,
457  34651, 34667, 34673, 34679, 34687, 34693, 34703, 34721, 34729, 34739,
458  34747, 34757, 34759, 34763, 34781, 34807, 34819, 34841, 34843, 34847,
459  34849, 34871, 34877, 34883, 34897, 34913, 34919, 34939, 34949, 34961,
460  34963, 34981, 35023, 35027, 35051, 35053, 35059, 35069, 35081, 35083,
461  35089, 35099, 35107, 35111, 35117, 35129, 35141, 35149, 35153, 35159,
462  35171, 35201, 35221, 35227, 35251, 35257, 35267, 35279, 35281, 35291,
463  35311, 35317, 35323, 35327, 35339, 35353, 35363, 35381, 35393, 35401,
464  35407, 35419, 35423, 35437, 35447, 35449, 35461, 35491, 35507, 35509,
465  35521, 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593,
466  35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753, 35759,
467  35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863,
468  35869, 35879, 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969,
469  35977, 35983, 35993, 35999, 36007, 36011, 36013, 36017, 36037, 36061,
470  36067, 36073, 36083, 36097, 36107, 36109, 36131, 36137, 36151, 36161,
471  36187, 36191, 36209, 36217, 36229, 36241, 36251, 36263, 36269, 36277,
472  36293, 36299, 36307, 36313, 36319, 36341, 36343, 36353, 36373, 36383,
473  36389, 36433, 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497,
474  36523, 36527, 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587,
475  36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683, 36691,
476  36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767, 36779, 36781,
477  36787, 36791, 36793, 36809, 36821, 36833, 36847, 36857, 36871, 36877,
478  36887, 36899, 36901, 36913, 36919, 36923, 36929, 36931, 36943, 36947,
479  36973, 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057,
480  37061, 37087, 37097, 37117, 37123, 37139, 37159, 37171, 37181, 37189,
481  37199, 37201, 37217, 37223, 37243, 37253, 37273, 37277, 37307, 37309,
482  37313, 37321, 37337, 37339, 37357, 37361, 37363, 37369, 37379, 37397,
483  37409, 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501, 37507,
484  37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567, 37571, 37573,
485  37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649, 37657, 37663,
486  37691, 37693, 37699, 37717, 37747, 37781, 37783, 37799, 37811, 37813,
487  37831, 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907, 37951,
488  37957, 37963, 37967, 37987, 37991, 37993, 37997, 38011, 38039, 38047,
489  38053, 38069, 38083, 38113, 38119, 38149, 38153, 38167, 38177, 38183,
490  38189, 38197, 38201, 38219, 38231, 38237, 38239, 38261, 38273, 38281,
491  38287, 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371,
492  38377, 38393, 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543,
493  38557, 38561, 38567, 38569, 38593, 38603, 38609, 38611, 38629, 38639,
494  38651, 38653, 38669, 38671, 38677, 38693, 38699, 38707, 38711, 38713,
495  38723, 38729, 38737, 38747, 38749, 38767, 38783, 38791, 38803, 38821,
496  38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903, 38917, 38921,
497  38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023, 39041,
498  39043, 39047, 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133,
499  39139, 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217, 39227,
500  39229, 39233, 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323,
501  39341, 39343, 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419,
502  39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511, 39521, 39541,
503  39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659, 39667,
504  39671, 39679, 39703, 39709, 39719, 39727, 39733, 39749, 39761, 39769,
505  39779, 39791, 39799, 39821, 39827, 39829, 39839, 39841, 39847, 39857,
506  39863, 39869, 39877, 39883, 39887, 39901, 39929, 39937, 39953, 39971,
507  39979, 39983, 39989, 40009, 40013, 40031, 40037, 40039, 40063, 40087,
508  40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153, 40163, 40169,
509  40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283,
510  40289, 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433,
511  40459, 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529, 40531,
512  40543, 40559, 40577, 40583, 40591, 40597, 40609, 40627, 40637, 40639,
513  40693, 40697, 40699, 40709, 40739, 40751, 40759, 40763, 40771, 40787,
514  40801, 40813, 40819, 40823, 40829, 40841, 40847, 40849, 40853, 40867,
515  40879, 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961, 40973,
516  40993, 41011, 41017, 41023, 41039, 41047, 41051, 41057, 41077, 41081,
517  41113, 41117, 41131, 41141, 41143, 41149, 41161, 41177, 41179, 41183,
518  41189, 41201, 41203, 41213, 41221, 41227, 41231, 41233, 41243, 41257,
519  41263, 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381, 41387,
520  41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491, 41507,
521  41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603,
522  41609, 41611, 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669,
523  41681, 41687, 41719, 41729, 41737, 41759, 41761, 41771, 41777, 41801,
524  41809, 41813, 41843, 41849, 41851, 41863, 41879, 41887, 41893, 41897,
525  41903, 41911, 41927, 41941, 41947, 41953, 41957, 41959, 41969, 41981,
526  41983, 41999, 42013, 42017, 42019, 42023, 42043, 42061, 42071, 42073,
527  42083, 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187,
528  42193, 42197, 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283,
529  42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359, 42373, 42379,
530  42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443, 42451, 42457,
531  42461, 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533, 42557,
532  42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649, 42667, 42677,
533  42683, 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743,
534  42751, 42767, 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841,
535  42853, 42859, 42863, 42899, 42901, 42923, 42929, 42937, 42943, 42953,
536  42961, 42967, 42979, 42989, 43003, 43013, 43019, 43037, 43049, 43051,
537  43063, 43067, 43093, 43103, 43117, 43133, 43151, 43159, 43177, 43189,
538  43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291, 43313, 43319,
539  43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441, 43451,
540  43457, 43481, 43487, 43499, 43517, 43541, 43543, 43573, 43577, 43579,
541  43591, 43597, 43607, 43609, 43613, 43627, 43633, 43649, 43651, 43661,
542  43669, 43691, 43711, 43717, 43721, 43753, 43759, 43777, 43781, 43783,
543  43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933,
544  43943, 43951, 43961, 43963, 43969, 43973, 43987, 43991, 43997, 44017,
545  44021, 44027, 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101,
546  44111, 44119, 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201,
547  44203, 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273, 44279,
548  44281, 44293, 44351, 44357, 44371, 44381, 44383, 44389, 44417, 44449,
549  44453, 44483, 44491, 44497, 44501, 44507, 44519, 44531, 44533, 44537,
550  44543, 44549, 44563, 44579, 44587, 44617, 44621, 44623, 44633, 44641,
551  44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729, 44741,
552  44753, 44771, 44773, 44777, 44789, 44797, 44809, 44819, 44839, 44843,
553  44851, 44867, 44879, 44887, 44893, 44909, 44917, 44927, 44939, 44953,
554  44959, 44963, 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077,
555  45083, 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181,
556  45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289, 45293, 45307,
557  45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377, 45389, 45403,
558  45413, 45427, 45433, 45439, 45481, 45491, 45497, 45503, 45523, 45533,
559  45541, 45553, 45557, 45569, 45587, 45589, 45599, 45613, 45631, 45641,
560  45659, 45667, 45673, 45677, 45691, 45697, 45707, 45737, 45751, 45757,
561  45763, 45767, 45779, 45817, 45821, 45823, 45827, 45833, 45841, 45853,
562  45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959, 45971, 45979,
563  45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099,
564  46103, 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199,
565  46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307, 46309,
566  46327, 46337, 46349, 46351, 46381, 46399, 46411, 46439, 46441, 46447,
567  46451, 46457, 46471, 46477, 46489, 46499, 46507, 46511, 46523, 46549,
568  46559, 46567, 46573, 46589, 46591, 46601, 46619, 46633, 46639, 46643,
569  46649, 46663, 46679, 46681, 46687, 46691, 46703, 46723, 46727, 46747,
570  46751, 46757, 46769, 46771, 46807, 46811, 46817, 46819, 46829, 46831,
571  46853, 46861, 46867, 46877, 46889, 46901, 46919, 46933, 46957, 46993,
572  46997, 47017, 47041, 47051, 47057, 47059, 47087, 47093, 47111, 47119,
573  47123, 47129, 47137, 47143, 47147, 47149, 47161, 47189, 47207, 47221,
574  47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309, 47317,
575  47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419,
576  47431, 47441, 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527,
577  47533, 47543, 47563, 47569, 47581, 47591, 47599, 47609, 47623, 47629,
578  47639, 47653, 47657, 47659, 47681, 47699, 47701, 47711, 47713, 47717,
579  47737, 47741, 47743, 47777, 47779, 47791, 47797, 47807, 47809, 47819,
580  47837, 47843, 47857, 47869, 47881, 47903, 47911, 47917, 47933, 47939,
581  47947, 47951, 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049,
582  48073, 48079, 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179,
583  48187, 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281, 48299,
584  48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397, 48407, 48409,
585  48413, 48437, 48449, 48463, 48473, 48479, 48481, 48487, 48491, 48497,
586  48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589, 48593, 48611,
587  48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733,
588  48751, 48757, 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817,
589  48821, 48823, 48847, 48857, 48859, 48869, 48871, 48883, 48889, 48907,
590  48947, 48953, 48973, 48989, 48991, 49003, 49009, 49019, 49031, 49033,
591  49037, 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121, 49123,
592  49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201, 49207, 49211,
593  49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331, 49333, 49339,
594  49363, 49367, 49369, 49391, 49393, 49409, 49411, 49417, 49429, 49433,
595  49451, 49459, 49463, 49477, 49481, 49499, 49523, 49529, 49531, 49537,
596  49547, 49549, 49559, 49597, 49603, 49613, 49627, 49633, 49639, 49663,
597  49667, 49669, 49681, 49697, 49711, 49727, 49739, 49741, 49747, 49757,
598  49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831, 49843, 49853,
599  49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957,
600  49991, 49993, 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069,
601  50077, 50087, 50093, 50101, 50111, 50119, 50123, 50129, 50131, 50147,
602  50153, 50159, 50177, 50207, 50221, 50227, 50231, 50261, 50263, 50273,
603  50287, 50291, 50311, 50321, 50329, 50333, 50341, 50359, 50363, 50377,
604  50383, 50387, 50411, 50417, 50423, 50441, 50459, 50461, 50497, 50503,
605  50513, 50527, 50539, 50543, 50549, 50551, 50581, 50587, 50591, 50593,
606  50599, 50627, 50647, 50651, 50671, 50683, 50707, 50723, 50741, 50753,
607  50767, 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857, 50867,
608  50873, 50891, 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971,
609  50989, 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109,
610  51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199, 51203,
611  51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329,
612  51341, 51343, 51347, 51349, 51361, 51383, 51407, 51413, 51419, 51421,
613  51427, 51431, 51437, 51439, 51449, 51461, 51473, 51479, 51481, 51487,
614  51503, 51511, 51517, 51521, 51539, 51551, 51563, 51577, 51581, 51593,
615  51599, 51607, 51613, 51631, 51637, 51647, 51659, 51673, 51679, 51683,
616  51691, 51713, 51719, 51721, 51749, 51767, 51769, 51787, 51797, 51803,
617  51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899,
618  51907, 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009,
619  52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121, 52127,
620  52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201, 52223, 52237,
621  52249, 52253, 52259, 52267, 52289, 52291, 52301, 52313, 52321, 52361,
622  52363, 52369, 52379, 52387, 52391, 52433, 52453, 52457, 52489, 52501,
623  52511, 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571, 52579,
624  52583, 52609, 52627, 52631, 52639, 52667, 52673, 52691, 52697, 52709,
625  52711, 52721, 52727, 52733, 52747, 52757, 52769, 52783, 52807, 52813,
626  52817, 52837, 52859, 52861, 52879, 52883, 52889, 52901, 52903, 52919,
627  52937, 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003, 53017,
628  53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101, 53113, 53117,
629  53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201, 53231,
630  53233, 53239, 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327,
631  53353, 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437, 53441,
632  53453, 53479, 53503, 53507, 53527, 53549, 53551, 53569, 53591, 53593,
633  53597, 53609, 53611, 53617, 53623, 53629, 53633, 53639, 53653, 53657,
634  53681, 53693, 53699, 53717, 53719, 53731, 53759, 53773, 53777, 53783,
635  53791, 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891,
636  53897, 53899, 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993,
637  54001, 54011, 54013, 54037, 54049, 54059, 54083, 54091, 54101, 54121,
638  54133, 54139, 54151, 54163, 54167, 54181, 54193, 54217, 54251, 54269,
639  54277, 54287, 54293, 54311, 54319, 54323, 54331, 54347, 54361, 54367,
640  54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421, 54437, 54443,
641  54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541,
642  54547, 54559, 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629,
643  54631, 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727, 54751,
644  54767, 54773, 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877,
645  54881, 54907, 54917, 54919, 54941, 54949, 54959, 54973, 54979, 54983,
646  55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073, 55079, 55103,
647  55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213, 55217,
648  55219, 55229, 55243, 55249, 55259, 55291, 55313, 55331, 55333, 55337,
649  55339, 55343, 55351, 55373, 55381, 55399, 55411, 55439, 55441, 55457,
650  55469, 55487, 55501, 55511, 55529, 55541, 55547, 55579, 55589, 55603,
651  55609, 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667, 55673,
652  55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763, 55787, 55793,
653  55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849,
654  55871, 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949,
655  55967, 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081, 56087,
656  56093, 56099, 56101, 56113, 56123, 56131, 56149, 56167, 56171, 56179,
657  56197, 56207, 56209, 56237, 56239, 56249, 56263, 56267, 56269, 56299,
658  56311, 56333, 56359, 56369, 56377, 56383, 56393, 56401, 56417, 56431,
659  56437, 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501, 56503,
660  56509, 56519, 56527, 56531, 56533, 56543, 56569, 56591, 56597, 56599,
661  56611, 56629, 56633, 56659, 56663, 56671, 56681, 56687, 56701, 56711,
662  56713, 56731, 56737, 56747, 56767, 56773, 56779, 56783, 56807, 56809,
663  56813, 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909,
664  56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983, 56989,
665  56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097,
666  57107, 57119, 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191,
667  57193, 57203, 57221, 57223, 57241, 57251, 57259, 57269, 57271, 57283,
668  57287, 57301, 57329, 57331, 57347, 57349, 57367, 57373, 57383, 57389,
669  57397, 57413, 57427, 57457, 57467, 57487, 57493, 57503, 57527, 57529,
670  57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641, 57649, 57653,
671  57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737,
672  57751, 57773, 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839,
673  57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943, 57947,
674  57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049, 58057, 58061,
675  58067, 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153, 58169,
676  58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229, 58231, 58237,
677  58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379,
678  58391, 58393, 58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453,
679  58477, 58481, 58511, 58537, 58543, 58549, 58567, 58573, 58579, 58601,
680  58603, 58613, 58631, 58657, 58661, 58679, 58687, 58693, 58699, 58711,
681  58727, 58733, 58741, 58757, 58763, 58771, 58787, 58789, 58831, 58889,
682  58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943, 58963, 58967,
683  58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053,
684  59063, 59069, 59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141,
685  59149, 59159, 59167, 59183, 59197, 59207, 59209, 59219, 59221, 59233,
686  59239, 59243, 59263, 59273, 59281, 59333, 59341, 59351, 59357, 59359,
687  59369, 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441, 59443,
688  59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513, 59539, 59557,
689  59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659,
690  59663, 59669, 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747,
691  59753, 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879, 59887,
692  59921, 59929, 59951, 59957, 59971, 59981, 59999, 60013, 60017, 60029,
693  60037, 60041, 60077, 60083, 60089, 60091, 60101, 60103, 60107, 60127,
694  60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217, 60223, 60251,
695  60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353,
696  60373, 60383, 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497,
697  60509, 60521, 60527, 60539, 60589, 60601, 60607, 60611, 60617, 60623,
698  60631, 60637, 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719,
699  60727, 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811,
700  60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913, 60917, 60919,
701  60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043,
702  61051, 61057, 61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169,
703  61211, 61223, 61231, 61253, 61261, 61283, 61291, 61297, 61331, 61333,
704  61339, 61343, 61357, 61363, 61379, 61381, 61403, 61409, 61417, 61441,
705  61463, 61469, 61471, 61483, 61487, 61493, 61507, 61511, 61519, 61543,
706  61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613, 61627, 61631,
707  61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717,
708  61723, 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861,
709  61871, 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979, 61981,
710  61987, 61991, 62003, 62011, 62017, 62039, 62047, 62053, 62057, 62071,
711  62081, 62099, 62119, 62129, 62131, 62137, 62141, 62143, 62171, 62189,
712  62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297, 62299, 62303,
713  62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459,
714  62467, 62473, 62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549,
715  62563, 62581, 62591, 62597, 62603, 62617, 62627, 62633, 62639, 62653,
716  62659, 62683, 62687, 62701, 62723, 62731, 62743, 62753, 62761, 62773,
717  62791, 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897, 62903,
718  62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987, 62989,
719  63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127,
720  63131, 63149, 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281,
721  63299, 63311, 63313, 63317, 63331, 63337, 63347, 63353, 63361, 63367,
722  63377, 63389, 63391, 63397, 63409, 63419, 63421, 63439, 63443, 63463,
723  63467, 63473, 63487, 63493, 63499, 63521, 63527, 63533, 63541, 63559,
724  63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617, 63629, 63647,
725  63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719,
726  63727, 63737, 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809,
727  63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913, 63929,
728  63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037, 64063, 64067,
729  64081, 64091, 64109, 64123, 64151, 64153, 64157, 64171, 64187, 64189,
730  64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301, 64303, 64319,
731  64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453,
732  64483, 64489, 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601,
733  64609, 64613, 64621, 64627, 64633, 64661, 64663, 64667, 64679, 64693,
734  64709, 64717, 64747, 64763, 64781, 64783, 64793, 64811, 64817, 64849,
735  64853, 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927, 64937,
736  64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033, 65053, 65063,
737  65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147,
738  65167, 65171, 65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267,
739  65269, 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371, 65381,
740  65393, 65407, 65413, 65419, 65423, 65437, 65447, 65449, 65479, 65497,
741  65519, 65521# 65537, 65539, 65543, 65551, 65557, 65563, 65579, 65581
742  ))
743 
744 
745 ## Primorielle tenant sur 32 bits
746 PRIMORIAL32_TUPLE = (1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870) # 6469693230
747 
748 
749 
750 # ###########
751 # Fonctions #
752 #############
753 ## Coefficient binomial de n et k
754 def binom(n, k):
755  """Renvoie le coefficient binomial (n)
756  (k)
757 
758  Pre: n: naturel < 2**32
759  k: naturel < 2**32 tels que le résultat < 2**32
760 
761  Result: naturel < 2**32
762 
763  O(n, k) = ..."""
764  assert DSPython.nat32_is(n), n
765  assert DSPython.nat32_is(k), k
766 
767  if k <= n:
768  import DSPython.natural as natural
769 
770  if n - k < k:
771  k = n - k
772  r = natural.falling_factorial_pow(n, k)
773  if k <= 12:
774  r //= FACTORIAL_TUPLE[k]
775  else:
776  r //= math.factorial(k)
777 
778  assert DSPython.nat32_is(r), (n, k, r)
779 
780  return r
781  else:
782  return 0
783 
784 
785 ## m et n sont premiers entre eux ?
786 def coprime_is(m, n):
787  """Renvoie True si m et n sont premiers entre eux,
788  False sinon
789  (Si m == n == 0 alors renvoie False)
790 
791  Pre: m: naturel < 2**32
792  n: naturel < 2**32
793 
794  Result: bool
795 
796  O(m, n) = ..."""
797  assert DSPython.nat32_is(m), m
798  assert DSPython.nat32_is(n), n
799 
800  return (not ((m&1 == 0) and (n&1 == 0))) and (fractions.gcd(m, n) == 1)
801 
802 
803 ## n est divisible par d ?
804 def divisible_is(n, d):
805  """Renvoie True si n est divisble par d, False sinon
806 
807  Pre: n: naturel < 2**32
808  d: 1 <= naturel < 2**32
809 
810  Result: bool
811 
812  O(n) = 1"""
813  assert DSPython.nat32_is(n), n
814  assert DSPython.nat32_is(d), d
815  assert d >= 1, d
816 
817  return n%d == 0
818 
819 
820 ## n!
821 def factorial(n):
822  """Renvoie n!, la factorielle de n
823  == 1 * 2 * 3 * ... * n
824  (Si n == 0 alors renvoie 1)
825 
826  Pre: n: naturel <= 12
827 
828  Result: 1 <= naturel <= 479001600 < 2**32
829 
830  O(n) = 1"""
831  assert DSPython.nat32_is(n), n
832  assert n <= 12, n
833 
834  return FACTORIAL_TUPLE[n]
835 
836 
837 ## k<sup>e</sup> puissance factorielle descendante de n
838 def falling_factorial_pow(n, k):
839  """Renvoie la kème puissance factorielle descendante de n
840  == n * (n - 1) * (n - 2) * ... * (n - k + 1)
841 
842  Pre: n: naturel < 2**32
843  k: naturel < 2**32 tels que le résultat < 2**32
844 
845  Result: naturel < 2**32
846 
847  O(n, k) = ..."""
848  assert DSPython.nat32_is(n), n
849  assert DSPython.nat32_is(k), k
850 
851  if n - 1 > k > 0: # n - 1 > k > 0
852  if n <= 12:
853  return FACTORIAL_TUPLE[n] // FACTORIAL_TUPLE[n - k]
854  else:
855  if __debug__:
856  _call_n = n
857  _call_k = k
858 
859  if k&1 == 0:
860  f = n * (n - 1)
861  n -= 2
862  k -= 2
863  else:
864  f = n
865  n -= 1
866  k >>= 1
867 
868  assert f <= bit32.MERSENNE32, (_call_n, _call_k, n, k, f)
869 
870  while k > 0: # multiplie les 2k facteurs restants
871  f *= n * (n - 1)
872  n -= 2
873  k -= 1
874 
875  assert f <= bit32.MERSENNE32, (_call_n, _call_k, n, k, f)
876 
877  return f
878  elif (n - 1 == k) or (n == k): # n = k + (0 ou 1)
879  return FACTORIAL_TUPLE[n]
880  elif k == 0: # n > 1, k = 0
881  return 1
882  else: # n < k > 0
883  return 0
884 
885 
886 ## F<sub>k</sub>
887 def fibonacci(k):
888  """Renvoie le nième nombre de Fibonacci F_k
889 
890  Pre: k: naturel <= 47
891 
892  Result: naturel <= 2971215073 < 2**32
893 
894  O(k) = 1"""
895  assert DSPython.nat32_is(k), k
896  assert k <= 47, k
897 
898  return FIBONACCI_TUPLE[k]
899 
900 
901 ## (F<sub>k-1</sub>, F<sub>k</sub>)
902 def fibonacci2(k):
903  """Renvoie (F_(k-1), F_k), les (k-1)ième et kième nombres de Fibonacci
904  (Si k == 0 alors renvoie (1, 0))
905 
906  Pre: k: naturel <= 47
907 
908  Result: couple de naturels <= 2971215073 < 2**32
909 
910  O(k) = 1"""
911  assert DSPython.nat32_is(k), k
912  assert k <= 47, k
913 
914  return (FIBONACCI_TUPLE[k - 1:k + 1] if k > 0
915  else (1, 0))
916 
917 
918 ## n est un nombre de Fibonacci ?
919 def fibonacci_is(n):
920  """Renvoie True si n est un nombre de Fibonacci,
921  False sinon
922 
923  Pre: n: naturel < 2**32
924 
925  Result: bool
926 
927  O(n) = 1"""
928  assert DSPython.nat32_is(n), n
929 
930  return n <= 2971215073 and FIBONACCI_TUPLE[bisect.bisect_left(FIBONACCI_TUPLE, n)] == n
931 
932 
933 ## Indice du nombre de Fibonacci correspondant à n, ou None
934 def fibonacci_to_index(n):
935  """Si n == F_k alors renvoie k
936  (si n == 1 alors renvoie toujours 1, jamais 2),
937  sinon renvoie None
938 
939  Pre: n: naturel < 2**32
940 
941  Result: naturel <= 47 ou None
942 
943  O(n) = 1"""
944  assert DSPython.nat32_is(n), n
945 
946  if n <= 2971215073:
947  k = bisect.bisect_left(FIBONACCI_TUPLE, n)
948  if FIBONACCI_TUPLE[k] == n:
949  return k
950  return None
951 
952 
953 ## PGCD de m et n (Plus Grand Commun Diviseur/ Greatest Common Divisor)
954 def gcd(m, n):
955  """Renvoie le PGCD de m et n
956  (Si m == n == 0 alors renvoie 0)
957  (Plus Grand Commun Diviseur/ Greatest Common Divisor)
958 
959  Pre: m: naturel < 2**32
960  n: naturel < 2**32
961 
962  Result: naturel < 2**32
963 
964  O(m, n) = ..."""
965  assert DSPython.nat32_is(m), m
966  assert DSPython.nat32_is(n), n
967 
968  return fractions.gcd(m, n)
969 
970 
971 ## PPCM de m et n (Plus Petit Commun Multiple/ Least Common Multiple)
972 def lcm(m, n):
973  """Renvoie le PPCM de m et n
974  (Si m == 0 ou n == 0 alors renvoie 0)
975  (Plus Petit Commun Multiple/ Least Common Multiple)
976 
977  Pre: m: naturel < 2**32
978  n: naturel < 2**32 tels que lcm(m, n) < 2**32
979 
980  Result: naturel < 2**32
981 
982  O(m, n) = ..."""
983  assert DSPython.nat32_is(m), m
984  assert DSPython.nat32_is(n), n
985 
986  return (m*n//fractions.gcd(m, n) if (m != 0) and (n != 0)
987  else 0)
988 
989 
990 ## L<sub>k</sub>
991 def lucas(k):
992  """Renvoie L_k, le kième nombre de Lucas
993 
994  Pre: k: naturel <= 46
995 
996  Result: naturel <= 4106118243
997 
998  O(k) = ..."""
999  assert DSPython.nat32_is(k), k
1000  assert k <= 46, k
1001 
1002  Fk_1, Fk= fibonacci2(k)
1003  return (Fk_1 << 1) + Fk
1004 
1005 
1006 ## (L<sub>k-1</sub>, L<sub>k</sub>)
1007 def lucas2(k):
1008  """Renvoie (L_(k-1), L_k), les (k-1)ième et kième nombres de Lucas
1009 
1010  Pre: k: naturel
1011 
1012  Result: (-1, 2) si k == 0, sinon couple de naturels <= 4106118243 < 2**32
1013 
1014  O(k) = ..."""
1015  assert DSPython.nat32_is(k), k
1016  assert k <= 46, k
1017 
1018  if k > 0:
1019  Fk_2, Fk_1= fibonacci2(k - 1)
1020  Fk = Fk_1 + Fk_2
1021  return (Fk + Fk_2, (Fk_1 << 1) + Fk)
1022  else:
1023  return (-1, 2)
1024 
1025 
1026 ## n est un nombre de Lucas ?
1027 def lucas_is(n):
1028  """Renvoie True si n est un nombre de Lucas,
1029  False sinon
1030 
1031  Pre: n: naturel < 2**32
1032 
1033  Result: bool
1034 
1035  O(n) = 1"""
1036  assert DSPython.nat32_is(n), n
1037 
1038  if (n != 2) and (n <= 4106118243):
1039  Lk_1, Lk = 2, 1
1040  while Lk < n:
1041  Lk_1, Lk = Lk, Lk + Lk_1
1042  return Lk == n
1043  else:
1044  return n == 2
1045 
1046 
1047 ## Indice du nombre de Lucas correspondant au naturel n, ou None
1048 def lucas_to_index(n):
1049  """Si n == L_k alors renvoie k
1050  sinon renvoie None
1051 
1052  Pre: n naturel < 2**32
1053 
1054  Result: naturel ou None
1055 
1056  O(n) = ..."""
1057  assert DSPython.nat32_is(n), n
1058 
1059  if (n != 2) and (n <= 4106118243):
1060  k = 1
1061  Lk_1, Lk = 2, 1
1062  while Lk < n:
1063  Lk_1, Lk = Lk, Lk + Lk_1
1064  k += 1
1065  if Lk == n:
1066  return k
1067  else:
1068  return None
1069  elif n == 2:
1070  return 0
1071  else:
1072  return None
1073 
1074 
1075 ## Produit des facteurs non communs de m et n (Not common Factors Product)
1076 def nfp(m, n):
1077  """Renvoie le produit des facteurs non communs de m et n
1078  (Si m == 0 ou n == 0 alors renvoie 0)
1079  (Not common Factors Product)
1080 
1081  Pre: m: naturel < 2**32
1082  n: naturel < 2**32
1083 
1084  Result: naturel < 2**32
1085 
1086  O(m, n) = ..."""
1087  assert DSPython.nat32_is(m), m
1088  assert DSPython.nat32_is(n), n
1089 
1090  return (m*n//(fractions.gcd(m, n)**2) if (m != 0) and (n != 0)
1091  else 0)
1092 
1093 
1094 ## 3<sup>k</sup>
1095 def pow3(k):
1096  """Renvoie la kième puissance de 3 : 3**k
1097 
1098  Pre: k naturel <= 20
1099 
1100  Result: 1 <= naturel <= 3**20 < 2**32
1101 
1102  O(k) = 1"""
1103  assert DSPython.nat32_is(k), k
1104  assert k <= 20, k
1105 
1106  return POW3_TUPLE[k]
1107 
1108 
1109 ## n est premier ?
1110 def prime_is(n):
1111  """Renvoie True si n est premier,
1112  False sinon
1113 
1114  Pre: n: naturel < 2**32
1115 
1116  Result: bool
1117 
1118  O(n) = ..."""
1119  assert DSPython.nat32_is(n), n
1120 
1121  if n&1 == 0: # les pairs
1122  return n == 2
1123  elif n <= 65521: # ceux qui sont dans la table
1124  return PRIME_16_ARRAY[bisect.bisect_left(PRIME_16_ARRAY, n)] == n
1125  else: # les autres
1126  m = n % PRIMORIAL32_TUPLE[4]
1127  if MODS_PRIMORIAL_4_TUPLE[bisect.bisect_left(MODS_PRIMORIAL_4_TUPLE, m)] != m:
1128  return False
1129  else:
1130  for p in PRIME_16_ARRAY[:bisect.bisect(PRIME_16_ARRAY, int(math.sqrt(n)))]:
1131  if divisible_is(n, p):
1132  return False
1133  return True
1134 
1135 
1136 ## Primorielle de n
1137 def primorial(n):
1138  """Renvoie la primorielle de n,
1139  c.-à-d. le produit des n premiers nombres premiers
1140  (Si n == 0 alors renvoie 1)
1141 
1142  Pre: n: naturel <= 9
1143 
1144  Result: 1 <= naturel <= 223092870 < 2**32
1145 
1146  O(n) = 1"""
1147  assert DSPython.nat32_is(n), n
1148  assert n <= 9, n
1149 
1150  return PRIMORIAL32_TUPLE[n]
1151 
1152 
1153 ## k<sup>e</sup> puissance factorielle montante de n
1154 def rising_factorial_pow(n, k):
1155  """Renvoie la kème puissance factorielle montante de n
1156  == n * (n + 1) * (n + 2) * ... * (n + k - 1)
1157 
1158  Pre: n: naturel < 2**32
1159  k: naturel < 2**32 tel que le résultat < 2**32
1160 
1161  Result: naturel < 2**32
1162 
1163  O(n, k) = ..."""
1164  assert DSPython.nat32_is(n), n
1165  assert DSPython.nat32_is(k), k
1166 
1167  if (n > 0) and (k > 0): # n, k > 0
1168  if n + k < 14: # n + k - 1 <= 12
1169  return FACTORIAL_TUPLE[n + k - 1] // FACTORIAL_TUPLE[n - 1]
1170  else:
1171  if __debug__:
1172  _call_n = n
1173  _call_k = k
1174 
1175  if k&1 == 0:
1176  f = n * (n + 1)
1177  n += 2
1178  k -= 2
1179  else:
1180  f = n
1181  n += 1
1182  k >>= 1
1183 
1184  assert f <= bit32.MERSENNE32, (_call_n, _call_k, n, k, f)
1185 
1186  while k > 0: # multiplie les 2k facteurs restants
1187  f *= n * (n + 1)
1188  n += 2
1189  k -= 1
1190 
1191  assert f <= bit32.MERSENNE32, (_call_n, _call_k, n, k, f)
1192 
1193  return f
1194  elif k == 0: # n >= k = 0
1195  return 1
1196  else: # n = 0 < k
1197  return 0
1198 
1199 
1200 
1201 # ######\cond MAINTEST
1202 # Main #
1203 ########
1204 if __name__ == '__main__':
1205  def main_test():
1206  """Test du module"""
1207  import sys
1208 
1209  try:
1210  if not 'profile' in dir():
1211  import psyco
1212  psyco.full()
1213  except ImportError:
1214  pass
1215 
1216  import DSPython.debug as debug
1217 
1218  debug.test_begin(VERSION, __debug__)
1219 
1220  print('len(FACTORIAL_TUPLE) == {0} ...'.format(len(FACTORIAL_TUPLE)), end='')
1221  assert len(FACTORIAL_TUPLE) == 13, len(FACTORIAL_TUPLE)
1222  print('ok'); sys.stdout.flush()
1223 
1224  print('len(FIBONACCI_TUPLE) == {0} ...'.format(len(FIBONACCI_TUPLE)), end='')
1225  assert len(FIBONACCI_TUPLE) == 48, len(FIBONACCI_TUPLE)
1226  print('ok'); sys.stdout.flush()
1227 
1228  print('len(POW3_TUPLE) == {0} ...'.format(len(POW3_TUPLE)), end='')
1229  assert len(POW3_TUPLE) == 21, len(POW3_TUPLE)
1230  print('ok'); sys.stdout.flush()
1231 
1232  print('len(PRIME_16_ARRAY) == {0} ...'.format(len(PRIME_16_ARRAY)), end='')
1233  assert len(PRIME_16_ARRAY) == 6542, len(PRIME_16_ARRAY)
1234  print('ok'); sys.stdout.flush()
1235 
1236  print('len(PRIMORIAL32_TUPLE) == {0} ...'.format(len(PRIMORIAL32_TUPLE)), end='')
1237  assert len(PRIMORIAL32_TUPLE) == 10, len(PRIMORIAL32_TUPLE)
1238  print('ok'); sys.stdout.flush()
1239 
1240 
1241  print('MODS_PRIMORIAL_1_TUPLE...', end=''); sys.stdout.flush()
1242  assert MODS_PRIMORIAL_1_TUPLE == (1)
1243  print('ok'); sys.stdout.flush()
1244 
1245  print('MODS_PRIMORIAL_2_TUPLE...', end=''); sys.stdout.flush()
1246  assert MODS_PRIMORIAL_2_TUPLE == (1, 5)
1247  l = [1]
1248  p = primorial(2)
1249  for m in range(2, p):
1250  if coprime_is(m, p):
1251  l.append(m)
1252  assert MODS_PRIMORIAL_2_TUPLE == tuple(l), (MODS_PRIMORIAL_2_TUPLE, l)
1253  print('ok'); sys.stdout.flush()
1254 
1255  print('MODS_PRIMORIAL_3_TUPLE...', end=''); sys.stdout.flush()
1256  assert len(MODS_PRIMORIAL_3_TUPLE) == 8, len(MODS_PRIMORIAL_3_TUPLE)
1257  l = [1]
1258  p = primorial(3)
1259  for m in range(2, p):
1260  if coprime_is(m, p):
1261  l.append(m)
1262  assert MODS_PRIMORIAL_3_TUPLE == tuple(l), (MODS_PRIMORIAL_3_TUPLE, l)
1263  print('ok'); sys.stdout.flush()
1264 
1265  print('MODS_PRIMORIAL_4_TUPLE...', end=''); sys.stdout.flush()
1266  assert len(MODS_PRIMORIAL_4_TUPLE) == 48, len(MODS_PRIMORIAL_4_TUPLE)
1267  l = [1]
1268  p = primorial(4)
1269  for m in range(2, p):
1270  if coprime_is(m, p):
1271  l.append(m)
1272  assert MODS_PRIMORIAL_4_TUPLE == tuple(l), (MODS_PRIMORIAL_4_TUPLE, l)
1273  print('ok'); sys.stdout.flush()
1274 
1275 
1276  print('MODS_PRIMORIAL_4_DIFF_TUPLE...', end=''); sys.stdout.flush()
1277  assert len(MODS_PRIMORIAL_4_DIFF_TUPLE) == 48, len(MODS_PRIMORIAL_4_DIFF_TUPLE)
1278  for i in range(len(MODS_PRIMORIAL_4_DIFF_TUPLE) - 1):
1279  assert MODS_PRIMORIAL_4_TUPLE[i+1] - MODS_PRIMORIAL_4_TUPLE[i] \
1280  == MODS_PRIMORIAL_4_DIFF_TUPLE[i], \
1281  (i, MODS_PRIMORIAL_4_TUPLE[i+1], MODS_PRIMORIAL_4_TUPLE[i],
1282  MODS_PRIMORIAL_4_DIFF_TUPLE[i], l)
1283  assert MODS_PRIMORIAL_4_DIFF_TUPLE[47] == 2, MODS_PRIMORIAL_4_DIFF_TUPLE[47]
1284  print('ok'); sys.stdout.flush()
1285 
1286 
1287  print('MODS_PRIMORIALS_TUPLE...', end=''); sys.stdout.flush()
1288  assert len(MODS_PRIMORIALS_TUPLE) == 4, len(MODS_PRIMORIALS_TUPLE)
1289  assert MODS_PRIMORIALS_TUPLE[0] == MODS_PRIMORIAL_1_TUPLE
1290  assert MODS_PRIMORIALS_TUPLE[1] == MODS_PRIMORIAL_2_TUPLE
1291  assert MODS_PRIMORIALS_TUPLE[2] == MODS_PRIMORIAL_3_TUPLE
1292  assert MODS_PRIMORIALS_TUPLE[3] == MODS_PRIMORIAL_4_TUPLE
1293  print('ok'); sys.stdout.flush()
1294 
1295 
1296  print()
1297  print('binom()...', end=''); sys.stdout.flush()
1298  for n in range(35):
1299  assert binom(n, 0) == 1, (n, binom(n, 0))
1300  assert binom(n, 1) == n, (n, binom(n, 1))
1301  for k in range(1, 10):
1302  assert binom(n, n+k) == 0, (n, k, binom(n, n+k))
1303  s = 0
1304  for k in range(n + 1):
1305  s += binom(n, k)
1306  assert s == 2**n, (n, s, 2**n)
1307  for n in range(1, 35):
1308  for k in range(1, n + 1):
1309  assert binom(n, k) == binom(n, n - k), (n, k, binom(n, k), binom(n, n - k))
1310  assert binom(n, k) == binom(n - 1, k - 1) * n // k, \
1311  (n, k, binom(n, k), binom(n - 1, k - 1))
1312  assert binom(n, k) == binom(n, k - 1) * (n - k + 1) // k, \
1313  (n, k, binom(n, k), binom(n, k - 1) * (n - k + 1))
1314  for n in range(3, 100):
1315  assert binom(n, 2) == ((n - 1)*n)//2, (n, binom(n, 2), ((n - 1)*n)//2)
1316  print('ok'); sys.stdout.flush()
1317 
1318 
1319  print('coprime_is()...', end=''); sys.stdout.flush()
1320  assert coprime_is(1, 1), coprime_is(1, 1)
1321  for m in range(50):
1322  if m != 1:
1323  assert not coprime_is(m, 0), (m, coprime_is(m, 0))
1324  assert coprime_is(m, 1) == 1, (m, coprime_is(m, 1))
1325  for p in PRIME_16_ARRAY:
1326  if m%p == 0:
1327  assert not coprime_is(m, p), (m, p, coprime_is(m, p))
1328  else:
1329  assert coprime_is(m, p) == 1, (m, p, coprime_is(m, p))
1330  if p > 3*m:
1331  break
1332  assert coprime_is(m, m + 1), m
1333  for m in range(50):
1334  for n in range(10):
1335  assert coprime_is(m, n) == coprime_is(n, m), \
1336  (m, n, coprime_is(m, n), fractions.gcd(n, m))
1337  print('ok'); sys.stdout.flush()
1338 
1339 
1340  print('divisible_is()...', end=''); sys.stdout.flush()
1341  for n in range(300):
1342  for d in range(1, 300):
1343  assert divisible_is(n, d) == (n%d == 0)
1344  print('ok'); sys.stdout.flush()
1345 
1346 
1347  print('factorial()...', end=''); sys.stdout.flush()
1348  assert factorial(0) == 1, factorial(0)
1349  f = 1
1350  for n in range(1, 13):
1351  f *= n
1352  assert factorial(n) == f, (n, factorial(n))
1353  assert factorial(n) == math.factorial(n), (n, factorial(n), math.factorial(n))
1354  print('ok'); sys.stdout.flush()
1355 
1356 
1357  print('falling_factorial_pow()...', end=''); sys.stdout.flush()
1358  assert falling_factorial_pow(0, 0) == 1, falling_factorial_pow(0, 0)
1359  for n in range(1625):
1360  assert falling_factorial_pow(n, 0) == 1, (n, falling_factorial_pow(n, 0))
1361  assert falling_factorial_pow(n, 1) == n, (n, falling_factorial_pow(n, 1))
1362  assert falling_factorial_pow(n, 2) == n*(n - 1), (n, falling_factorial_pow(n, 2))
1363  assert falling_factorial_pow(n, 3) == n*(n - 1)*(n - 2), \
1364  (n, falling_factorial_pow(n, 3))
1365  assert falling_factorial_pow(n, n + 1) == 0, (n, falling_factorial_pow(n, n+1))
1366  for k in range(13):
1367  assert falling_factorial_pow(k, k) == factorial(k), \
1368  (k, factorial(k), falling_factorial_pow(k, k))
1369  for k in range(12):
1370  assert falling_factorial_pow(k + 1, k) == factorial(k + 1), \
1371  (k, factorial(k + 1), falling_factorial_pow(2, k))
1372  for k in range(1, 100):
1373  assert falling_factorial_pow(0, k) == 0, (k, falling_factorial_pow(0, k))
1374  for k in range(1, 12):
1375  for n in range(k, min(100, int(pow(bit32.MERSENNE32, 1/k)) + 3)):
1376  assert falling_factorial_pow(n, k) \
1377  == math.factorial(n)//math.factorial(n - k), \
1378  (n, k,
1379  math.factorial(n + k - 1)//math.factorial(n - 1),
1380  falling_factorial_pow(n, k))
1381  print('ok'); sys.stdout.flush()
1382 
1383 
1384  print('fibonacci()...', end=''); sys.stdout.flush()
1385  assert fibonacci(0) == 0, fibonacci(0)
1386  Fk_1 = 1
1387  Fk = 0
1388  for k in range(48):
1389  assert fibonacci(k) == Fk, (n, fibonacci(k))
1390  Fk_1, Fk = Fk, Fk + Fk_1
1391  print('ok'); sys.stdout.flush()
1392 
1393 
1394  print('fibonacci2()...', end=''); sys.stdout.flush()
1395  assert fibonacci2(0) == (1, 0), fibonacci2(0)
1396  Fk_1 = 1
1397  Fk = 0
1398  for k in range(48):
1399  assert fibonacci2(k) == (Fk_1, Fk), (k, fibonacci2(k))
1400  Fk_1, Fk = Fk, Fk + Fk_1
1401  print('ok'); sys.stdout.flush()
1402 
1403 
1404  print('fibonacci_is()...', end=''); sys.stdout.flush()
1405  assert fibonacci_is(0)
1406  assert fibonacci_is(1)
1407  assert fibonacci_is(2)
1408  assert fibonacci_is(3)
1409  assert not fibonacci_is(4)
1410  for k in range(3, 48):
1411  assert fibonacci_is(fibonacci(k)), (k, fibonacci(k))
1412  for n in range(32768):
1413  if fibonacci_is(n):
1414  assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
1415  else:
1416  assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
1417  for n in range(1, 2**32, 1000000):
1418  if fibonacci_is(n):
1419  assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
1420  else:
1421  assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
1422  for n in range(2**32-32768, 2**32):
1423  if fibonacci_is(n):
1424  assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
1425  else:
1426  assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
1427  print('ok'); sys.stdout.flush()
1428 
1429 
1430  print('fibonacci_to_index()...', end=''); sys.stdout.flush()
1431  assert fibonacci_to_index(0) == 0, fibonacci_to_index(0)
1432  assert fibonacci_to_index(1) == 1, fibonacci_to_index(1)
1433  assert fibonacci_to_index(2) == 3, fibonacci_to_index(2)
1434  assert fibonacci_to_index(3) == 4, fibonacci_to_index(3)
1435  assert fibonacci_to_index(4) == None, fibonacci_to_index(4)
1436  for k in range(3, 48):
1437  assert fibonacci_to_index(fibonacci(k)) == k, \
1438  (k, fibonacci(k), fibonacci_to_index(fibonacci(k)))
1439  for n in range(32768):
1440  k = fibonacci_to_index(n)
1441  if k != None:
1442  assert fibonacci(k) == n, (n, k, fibonacci(k))
1443  for n in range(1, 2**32, 1000000):
1444  k = fibonacci_to_index(n)
1445  if k != None:
1446  assert fibonacci(k) == n, (n, k, fibonacci(k))
1447  for n in range(2**32-32768, 2**32):
1448  k = fibonacci_to_index(n)
1449  if k != None:
1450  assert fibonacci(k) == n, (n, k, fibonacci(k))
1451  print('ok'); sys.stdout.flush()
1452 
1453 
1454  print('gcd()...', end=''); sys.stdout.flush()
1455  for m in range(100):
1456  assert gcd(m, 0) == m, (m, gcd(m, 0))
1457  assert gcd(m, 1) == 1, (m, gcd(m, 1))
1458  assert gcd(0, m) == m, (m, gcd(0, m))
1459  assert gcd(1, m) == 1, (m, gcd(1, m))
1460  assert gcd(m, m) == m, (m, gcd(m, m))
1461  for p in PRIME_16_ARRAY[:1000]:
1462  if m%p == 0:
1463  assert gcd(m, p) == p, (m, p, gcd(m, p))
1464  else:
1465  assert gcd(m, p) == 1, (m, p, gcd(m, p))
1466  for m in range(100):
1467  for n in range(100):
1468  assert gcd(m, n) == fractions.gcd(m, n), (m, n, gcd(m, n), fractions.gcd(m, n))
1469  assert gcd(m, n) == gcd(n, m), (m, n, gcd(m, n), gcd(n, m))
1470  print('ok'); sys.stdout.flush()
1471 
1472 
1473  print('lcm()...', end=''); sys.stdout.flush()
1474  for m in range(100):
1475  assert lcm(m, 0) == 0, (m, lcm(m, 0))
1476  assert lcm(m, 1) == m, (m, lcm(m, 1))
1477  assert lcm(0, m) == 0, (m, lcm(0, m))
1478  assert lcm(1, m) == m, (m, lcm(1, m))
1479  assert lcm(m, m) == m, (m, lcm(m, m))
1480  for p in PRIME_16_ARRAY[:1000]:
1481  if m%p == 0:
1482  assert lcm(m, p) == m, (m, p, lcm(m, p))
1483  else:
1484  assert lcm(m, p) == m * p, (m, p, lcm(m, p))
1485  for m in range(100):
1486  for n in range(100):
1487  assert lcm(m, n) == lcm(n, m), (m, n, lcm(m, n), lcm(n, m))
1488  assert lcm(m, n)*fractions.gcd(m, n) == m*n, (m, n, lcm(m, n), fractions.gcd(n, m),
1489  lcm(m, n)*fractions.gcd(n, m), m*n)
1490  print('ok'); sys.stdout.flush()
1491 
1492 
1493  print('lucas()...', end=''); sys.stdout.flush()
1494  Lk_1 = -1
1495  Lk = 2
1496  for k in range(47):
1497  assert lucas(k) == Lk, (k, lucas(k))
1498  Lk_1, Lk = Lk, Lk + Lk_1
1499  print('ok'); sys.stdout.flush()
1500 
1501 
1502  print('lucas2()...', end=''); sys.stdout.flush()
1503  assert lucas2(0) == (-1, 2), lucas2(0)
1504  assert lucas2(1) == (2, 1), lucas2(1)
1505  assert lucas2(2) == (1, 3), lucas2(2)
1506  assert lucas2(3) == (3, 4), lucas2(3)
1507  Lk_1 = -1
1508  Lk = 2
1509  for k in range(47):
1510  assert lucas2(k) == (Lk_1, Lk), (k, lucas2(k))
1511  Lk_1, Lk = Lk, Lk + Lk_1
1512  print('ok'); sys.stdout.flush()
1513 
1514 
1515  print('lucas_is()...', end=''); sys.stdout.flush()
1516  assert not lucas_is(0)
1517  assert lucas_is(1)
1518  assert lucas_is(2)
1519  assert lucas_is(3)
1520  assert lucas_is(4)
1521  assert not lucas_is(5)
1522  for k in range(3, 47):
1523  assert lucas_is(lucas(k)), (k, lucas(k))
1524  for n in range(32768):
1525  if lucas_is(n):
1526  assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
1527  else:
1528  assert lucas_to_index(n) == None, (n, lucas_to_index(n))
1529  for n in range(1, 2**32, 1000000):
1530  if lucas_is(n):
1531  assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
1532  else:
1533  assert lucas_to_index(n) == None, (n, lucas_to_index(n))
1534  for n in range(2**32-32768, 2**32):
1535  if lucas_is(n):
1536  assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
1537  else:
1538  assert lucas_to_index(n) == None, (n, lucas_to_index(n))
1539  print('ok'); sys.stdout.flush()
1540 
1541 
1542  print('lucas_to_index()...', end=''); sys.stdout.flush()
1543  assert lucas_to_index(0) == None, lucas_to_index(0)
1544  assert lucas_to_index(1) == 1, lucas_to_index(1)
1545  assert lucas_to_index(2) == 0, lucas_to_index(2)
1546  assert lucas_to_index(3) == 2, lucas_to_index(3)
1547  assert lucas_to_index(4) == 3, lucas_to_index(4)
1548  assert lucas_to_index(5) == None, lucas_to_index(5)
1549  for k in range(3, 47):
1550  assert lucas_to_index(lucas(k)) == k, (k, lucas_to_index(lucas(k)))
1551  for n in range(32768):
1552  k = lucas_to_index(n)
1553  if k != None:
1554  assert lucas(k) == n, (n, k, lucas(k))
1555  for n in range(1, 2**32, 1000000):
1556  k = lucas_to_index(n)
1557  if k != None:
1558  assert lucas(k) == n, (n, k, lucas(k))
1559  for n in range(2**32 - 32768, 2**32):
1560  k = lucas_to_index(n)
1561  if k != None:
1562  assert lucas(k) == n, (n, k, lucas(k))
1563  print('ok'); sys.stdout.flush()
1564 
1565 
1566  print('nfp()...', end=''); sys.stdout.flush()
1567  for m in range(100):
1568  assert nfp(m, 0) == 0, (m, nfp(m, 0))
1569  assert nfp(m, 1) == m, (m, nfp(m, 1))
1570  assert nfp(0, m) == 0, (m, nfp(0, m))
1571  assert nfp(1, m) == m, (m, nfp(1, m))
1572  if m > 0:
1573  assert nfp(m, m) == 1, (m, nfp(m, m))
1574  for p in PRIME_16_ARRAY[:1000]:
1575  if m%p == 0:
1576  assert nfp(m, p) == m // p, (m, p, nfp(m, p))
1577  else:
1578  assert nfp(m, p) == m * p, (m, p, nfp(m, p))
1579  for m in range(100):
1580  for n in range(100):
1581  assert nfp(m, n) == nfp(n, m), (m, n, nfp(m, n), nfp(n, m))
1582  assert nfp(m, n)*(fractions.gcd(m, n)**2) == m * n, \
1583  (m, n, nfp(m, n), fractions.gcd(n, m)**2,
1584  nfp(m, n)*(fractions.gcd(n, m)**2), m*n)
1585  print('ok'); sys.stdout.flush()
1586 
1587 
1588  print('pow3()...', end=''); sys.stdout.flush()
1589  for k in range(21):
1590  assert pow3(k) == 3**k, (k, pow3(k))
1591  print('ok'); sys.stdout.flush()
1592 
1593 
1594  print('prime_is()...', end=''); sys.stdout.flush()
1595  assert not prime_is(0)
1596  assert not prime_is(1)
1597  assert prime_is(2)
1598  assert prime_is(3)
1599  assert not prime_is(4)
1600  assert prime_is(5)
1601  for n in range(2, 2**8):
1602  p_is = True
1603  for d in range(2, n):
1604  if n%d == 0:
1605  p_is = False
1606  break
1607  assert prime_is(n) == p_is, (n, prime_is(n), p_is)
1608  for n in range(6, 2**16+16384, 6):
1609  s = int(math.sqrt(n+5))
1610  p1_is = p5_is = True
1611  for p in PRIME_16_ARRAY:
1612  if p > s:
1613  break
1614  elif (n + 1)%p == 0:
1615  p1_is = False
1616  if not p5_is:
1617  break
1618  elif (n + 5)%p == 0:
1619  p5_is = False
1620  if not p1_is:
1621  break
1622  assert not prime_is(n), n
1623  assert prime_is(n + 1) == p1_is, (n + 1, prime_is(n + 1), p1_is)
1624  assert not prime_is(n + 2), n + 2
1625  assert not prime_is(n + 3), n + 3
1626  assert not prime_is(n + 4), n + 4
1627  assert prime_is(n + 5) == p5_is, (n + 5, prime_is(n + 5), p5_is)
1628  assert not prime_is(65530)
1629  assert prime_is(65521)
1630  for n in range(65522, 65537):
1631  assert not prime_is(n), n
1632  assert prime_is(2**32 - 17)
1633  for i in range(6, 17):
1634  assert not prime_is(2**32 - i)
1635  assert prime_is(2**32 - 5)
1636  for i in range(1, 5):
1637  assert not prime_is(2**32 - i)
1638  print('ok'); sys.stdout.flush()
1639 
1640 
1641  print('primorial()...', end=''); sys.stdout.flush()
1642  assert primorial(0) == 1, primorial(0)
1643  p = 1
1644  for n in range(10):
1645  assert primorial(n) == p, (n, primorial(n), p)
1646  p *= PRIME_16_ARRAY[n]
1647  print('ok'); sys.stdout.flush()
1648 
1649 
1650  print('rising_factorial_pow()...', end=''); sys.stdout.flush()
1651  assert rising_factorial_pow(0, 0) == 1, rising_factorial_pow(0, 0)
1652  for n in range(1625):
1653  assert rising_factorial_pow(n, 0) == 1, (n, rising_factorial_pow(n, 0))
1654  assert rising_factorial_pow(n, 1) == n, (n, rising_factorial_pow(n, 1))
1655  assert rising_factorial_pow(n, 2) == n*(n + 1), (n, rising_factorial_pow(n, 2))
1656  assert rising_factorial_pow(n, 3) == n*(n + 1)*(n + 2), (n, rising_factorial_pow(n, 3))
1657  for k in range(13):
1658  assert rising_factorial_pow(1, k) == factorial(k), \
1659  (k, factorial(k), rising_factorial_pow(1, k))
1660  for k in range(12):
1661  assert rising_factorial_pow(2, k) == factorial(k + 1), \
1662  (k, factorial(k+1), rising_factorial_pow(2, k))
1663  for k in range(1, 12):
1664  assert rising_factorial_pow(0, k) == 0, (k, rising_factorial_pow(0, k))
1665  for n in range(1, min(100, int(pow(bit32.MERSENNE32, 1/k) - k + 4))):
1666  assert rising_factorial_pow(n, k) \
1667  == math.factorial(n + k - 1)//math.factorial(n - 1), \
1668  (n,
1669  math.factorial(n + k - 1)//math.factorial(n - 1),
1670  rising_factorial_pow(n, k))
1671  print('ok'); sys.stdout.flush()
1672  debug.test_end()
1673 
1674  main_test()
1675 ##\endcond MAINTEST