Partir en récursion

Je viens de proposer ce papier au HS que la revue Tangente

consacrera en novembre au thème « Récursivité et processus itératifs ».

____________________

Itérer une spirale de chiffres

Nous allons illustrer une jolie itération « vers le haut » à l’aide d’une spirale de chiffres.

Cette spirale S est construite à partir d’une suite D classique de nombres distincts (l’ordre de ses termes sera expliqué plus loin) :

D = 0, 1, 3, 2, 5, 7, 9, 4, 10, 6, 8, 21, 11, 20, 22, 23, 13, 24, 26, 28, 40, 42, 44, 25, 15, 17, 46, 48, 60, 62, 19, 31, 12, 33, 27, 35, 29, 14, 64, 66, 16, 37, 68, 41, 80, 18, 82, 84, 86, 43, 30, 88, 32, 200, 45, 34, 202, 47, 49, 201, 204, 36, 61, 206, 208, 220, 222, 63, 39, 65, 51, 67, 53, 224, 226, 228, 240, 69, 55, 81, 57, 203, 205, 59, 83, 71, 73, 85, 75, 38, 50, 242, 87, 89, 244, 77, 79, 210, 91, 52, 54, 93, 212, 56, 58, 70, 214, 216, 207, 218, 72, 74, 76, 78, 95, 211, …

La succession des chiffres de D constitue la spirale S de chiffres :

S = 0, 1, 3, 2, 5, 7, 9, 4, 1, 0, 6, 8, 2, 1, 1, 1, 2, 0, 2, 2, 2, 3, 1, 3, 2, 4, 2, 6, 2, 8, 4, 0, 4, 2, 4, 4, 2, 5, 1, 5, 1, 7, 4, 6, 4, 8, 6, 0, 6, 2, 1, 9, 3, 1, 1, 2, 3, 3, 2, 7, 3, 5, 2, 9, 1, 4, 6, 4, 6, 6, 1, 6, 3, 7, 6, 8, 4, 1, 8, 0, 1, 8, 8, 2, 8, 4, 8, 6, 4, 3, 3, 0, 8, 8, 3, 2, 2, 0, 0, 4, 5, 3, 4, 2, 0, 2, 4, 7, 4, 9, 2, 0, 1, 2, 0, 4, 3, 6, 6, 1, 2, 0, 6, 2, 0, 8, 2, 2, 0, 2, 2, 2, 6, 3, 3, 9, 6, 5, 5, 1, 6, 7, 5, 3, 2, 2, 4, 2, 2, 6, 2, 2, 8, 2, 4, 0, 6, 9, 5, 5, 8, 1, 5, 7, 2, 0, 3, 2, 0, 5, 5, 9, 8, 3, 7, 1, 7, 3, 8, 5, 7, 5, 3, 8, 5, 0, 2, 4, 2, 8, 7, 8, 9, 2, 4, 4, 7, 7, 7, 9, 2, 1, 0, 9, 1, 5, 2, 5, 4, 9, 3, 2, 1, 2, 5, 6, 5, 8, 7, 0, 2, 1, 4, 2, 1, 6, 2, 0, 7, 2, 1, 8, 7, 2, 7, 4, 7, 6, 7, 8, 9, 5, 2, 1, 1, …

Ces chiffres seront dessinés d’une façon particulière. Nous leur avons choisi une fonte très simple (et vaguement « brutaliste ») – celle qui fut retenue par Dean Hickerson et quelques autres passionnés du Jeu de la Vie (voir les « nombres qui meurent au Jeu de la Vie » : https://oeis.org/A126803). Les chiffres de 0 à 9 s’inscrivent ainsi dans un rectangle vertical de 3 par 5 :

La spirale peut démarrer ; on met le zéro de la suite dans une case quelconque d’un plan quadrillé infini et on enroule S dans le sens des aiguilles d’une montre (un chiffre par case) :

Et voici le tour de passe-passe ; quand on met en couleur les chiffres impairs de la spirale (et rien qu’eux), on voit réapparaître le zéro « brutaliste » de départ :

En continuant à enrouler S ainsi (un chiffre par case dans le sens horloger et tous les chiffres impairs en couleur), on reconstitue à l’échelle supérieure la spirale elle-même. Les chiffres colorés ci-dessous sont les neuf chiffres tout au centre de la spirale :

Et ainsi de suite : les grands chiffres jaunes ci-dessus constituent eux-mêmes l’embryon du très grand zéro du niveau suivant ! On pourra donc dézoomer (ou zoomer) à l’infini à partir du petit zéro central – la spirale changera d’échelle mais reviendra toujours.

Cet exercice n’a rien de mathématique – il s’agit juste d’une astuce graphique où le dessin des chiffres de la base 10 est mis au service d’une récursivité particulière. Une autre fonte aurait donné une autre suite D de départ. Le comble étant que la D que nous venons d’analyser n’est même pas la lexico-première de son espèce ! On pourrait en effet construire une « auto-spirale » à partir du début D₂ = 0, 1, 2, 4, 3,… (ce début bat celui de D qui est 0, 1, 3, 2, 5,…)
Mais nous avons écarté D₂ car D₂, au lieu de commencer à l’intérieur et au centre de son propre zéro (comme D), commence juste au-dessus. Il s’agit encore ici d’un choix « esthétique » – assez éloigné des mathématiques « pures ».
Notons que D n’est pas une permutation des entiers non négatifs : tout nombre contenant en effet plus de 5 chiffres consécutifs impairs ne peut y figurer (le dessin des 0, 1, 3, 6, 7, 8 et 9 de D inclut une verticale de 5 chiffres – c’est le maximum possible sur la grille). Et précisons encore que la lexico-première suite D produisant ce type d’auto-spirale semble tout aussi impossible à trouver – mais c’est un autre débat !

La suite D est à présent dans l’OEIS, ici.

Update du 29 novembre 2020

Jean-Marc Falcoz, de son côté, calcule plus de termes grâce à un algorithme-maison. Ceci permettra à Jos Leys (si ce dernier dit oui !) de produire une animation « fractale ».

La « matrice » où figurent les chiffres (jaunes ci-dessus) que dessinent les « 1 » du programme de Jean-Marc est visible :

[Une explication basée sur un e-mail envoyé à Jean-Marc Falcoz il y a quelques jours]

(…)

Bon, je vais essayer d’expliquer la construction de la spirale auto-spirale.

a/ choisir une fonte pour dessiner les chiffres des nombres présents dans S (c’est celle-ci-dessous)

b/ décider que la suite S sera composée d’entiers tous distincts

c/ dessiner un plan infini au « quadrillage » régulier ; décider que ce quadrillage sera constitué de rectangles verticaux 6 X 4, dans lesquels s’inscriront plus tard les chiffres ci-dessus (chiffres « brutalistes » s’inscrivant eux-mêmes dans un rectangle 5 X 3) ; voici un bout de ce plan infini :

d/ dessiner un zéro sur ce plan (avec 12 croix) ; ce zéro est dessiné selon la fonte ci-dessus (visible aussi ici : https://oeis.org/A337405) ;

e/ décider que le centre géométrique de ce zéro a pour coordonnées (0,0) : c’est à partir de ce point (0,0) que s’orientera toute la future spirale ;

f/ décider que la suite de nombres S (encore inexistante, mais dont nous savons que les termes seront tous distincts) sera transformée en suite T de chiffres, T étant la succession des chiffres de S ;

g/ faire commencer S et T par 0 ;

h/ écrire le chiffre 0 dans la case de coordonnées (0,0) ;

i/ décider que la spirale de chiffres tournera dans le sens horloger et que le second chiffre de T sera dans le carré immédiatement à droite du carré de 0 ;

j/ se rendre compte que cette case est déjà marquée d’une croix ; décider que les chiffres de T qui occupent une case marquée d’une croix doivent être impairs ;

k/ en déduire que les cases sans croix seront occupées par des chiffres pairs de T [et se réjouir que le hasard fait bien les choses car le premier chiffre de T (zéro) est bien pair et dans une case sans croix !-]

l/ la lexico-condition qui gouverne S (donc T) oblige à mettre 1 à droite de zéro (1 occupe bien une case avec croix et 1 est le plus petit impair disponible) ;

m/ comprendre que la condition « spirale carrée horlogère » oblige à mettre le chiffre suivant de T sous le 1 ;

n/ comprendre que ce chiffre doit être impair (case avec croix) et égal à 3 (plus petit lexico-disponible) ;

o/ comprendre que le chiffre suivant doit être pair (il est dans une case sans croix), placé à gauche de 3 (condition spirale), et égal à 2 (plus petit lexico-dispo) ;

p/ comprendre que le chiffre suivant doit être impair (il est dans une case avec croix), placé à gauche de 2 (condition spirale), et égal à 5 (plus petit lexico-dispo) ;

q/ comprendre que le chiffre suivant doit être impair (il est dans une case avec croix), placé au-dessus de 5 (condition spirale), et égal à 7 (plus petit lexico-dispo) ;

r/ comprendre que le chiffre suivant doit être impair (il est dans une case avec croix), placé au-dessus de 7 (condition spirale), et égal à 9 (plus petit lexico-dispo) ;

s/ comprendre que le chiffre suivant doit être pair (il est dans une case sans croix), placé à droite du 9 (condition spirale), et égal à 4 (plus petit lexico-dispo) ;

t/ jeter un œil à la suite T qui se forme depuis le début sans oublier que T vient de S :

T = 0,1,3,2,5,7,9,4, ...

S = 0,1,3,2,5,7,9,4, ...

u/ comprendre que le terme suivant (appelons-le « k ») de S sera 10 (un nombre à deux chiffres) ; en effet le premier chiffre de ce terme doit être impair (ce chiffre alimentera T et finira sur une case avec croix). Or tous les nombres impairs n’ayant qu’un seul chiffre figurent déjà dans S, il *faut* donc que ce terme k ait plus qu’un chiffre ; et comme le second chiffre de k sera dans une case sans croix, il faut que S soit prolongée par k = 10 ; on a donc :

S = 0,1,3,2,5,7,9,4,10, ...

T = 0,1,3,2,5,7,9,4,1,0, ...

… et ceci se traduit par la spirale (simplifiée) :

v/ se poser soudain la question des « croix » : qui décide de mettre des croix dans telle case du plan et pas dans telle autre (il y a encore 6 croix ci-dessus) ?

w/ comprendre que c’est la suite T elle-même qui fixe, au fur et à mesure de son extension, la nature des cases « avec croix » ; voici en effet la « loi des croix » :

LES CROIX DOIVENT DESSINER LA SUITE T AU « NIVEAU 1 »

x/ le niveau 1 est un « quadrillage » où chaque rectangle de base est un rectangle vertical qui a pour côtés [4 carrés de niveau 0] sur [6 carrés de niveau 0] ; les chiffres (selon la fonte décrite en a/) s’inscrivent tous dans ce rectangle de base dont la rangée du bas et la colonne de gauche ne pourront JAMAIS comporter de croix (cases « n » grises ci-dessous avec « n » pour non) — ceci afin que les chiffres du niveau 1 ne soient pas « collés » les uns contre les autres et restent bien lisibles) :

On comprend donc que le tout premier chiffre de S (et de T, soit zéro) a dessiné le réseau de croix suivant (les « n » gris ne servent qu’à indiquer les cases interdites de croix quand on dessine un chiffre, quel qu’il soit, dans le rectangle-de-base 6 x 4) :

y/ comprendre soudain que la suite T, dont nous connaissons déjà les termes 0,1,3,2,5,7,9,4,1,0,... DESSINE un réseau de 10 chiffres « avec des croix » au niveau 1 ! Voici ce dessin (les « n » gris sont « invisibles » et ne matérialisent que des bandes interdites de croix) :

Le même dessin sans les « n » :

On voit ici le « réseau de croix » qui détermine les chiffres impairs à venir (les croix) et pairs (les points-qui-ne-sont-pas-des-n-invisibles) ; le réseau de croix SE DÉVELOPPE DONC EN MÊME TEMPS QUE LA SUITE DE CHIFFRES DE T. Et cela ne laisse plus aucun choix : les deux suites S et T sont désormais entièrement déterminées ! Les « X » ci-dessus dessinent, en commençant en haut à gauche, les chiffres :

9 - 4 - 1 - 0

7 - 0 - 1

5 - 2 - 3 ... qui sont précisément ceux de la spirale de départ. En voici une autre illustration, assez parlante, avec le début de la spirale au centre — et les croix qui attendent le déploiement de ladite spirale de chiffres :

On voit que la suite de la spirale sera donnée par les chiffres 6 - 8 - 2 - 1 - 1 - 1 - 2 - 0 - 2 - 2 - 2 - 3 ...

Notons que « l’arbitre des élégances » est bien la suite S d’abord ! C’est elle qui sait quand un nombre figure déjà dans S (et que ce nombre ne peut « revenir » puisque, par définition, tous les termes de S doivent être distincts). Il y a donc une triple interaction entre S, T et le « quadrillage » marqué de X où spiralent T et S.

__________

Jean-Marc a tout compris sans même lire le dixième des explications ci-dessus et calculé en un clin d’œil 1628 termes de S :

s={0,1,3,2,5,7,9,4,10,6,8,21,11,20,22,23,13,24,26,28,40,42,44,25,15,17,46,48,60,62,19,31,12,33,27,35,29,14,64,66,16,37,68,41,80,18,82,84,86,43,30,88,32,200,45,34,202,47,49,201,204,36,61,206,208,220,222,63,39,65,51,67,53,224,226,228,240,69,55,81,57,203,205,59,83,71,73,85,75,38,50,242,87,89,244,77,79,210,91,52,54,93,212,56,58,70,214,216,207,218,72,74,76,78,95,211,90,97,92,99,94,110,209,230,96,98,101,213,215,103,232,234,217,111,112,105,114,113,116,246,248,260,262,264,266,115,118,117,236,119,238,268,280,282,284,286,288,400,402,404,406,408,420,221,130,250,223,422,100,131,424,426,428,440,442,444,446,133,219,102,104,135,231,106,252,137,233,139,254,151,235,256,448,108,258,225,227,460,270,462,464,153,272,466,468,132,120,480,122,124,229,274,482,484,107,276,109,278,121,290,123,125,134,292,241,486,126,155,237,294,157,136,127,296,159,138,488,129,150,171,243,245,152,173,239,175,251,141,298,177,253,143,255,154,128,410,412,247,600,140,249,414,257,142,602,261,259,144,604,606,608,416,263,620,146,148,265,622,145,418,624,626,628,640,642,644,646,648,660,179,271,160,162,430,267,269,156,191,662,664,666,668,680,682,684,686,688,281,158,193,273,164,166,195,275,147,432,800,802,197,434,149,436,804,806,808,820,822,824,826,828,840,842,844,846,848,860,199,438,311,170,313,450,315,452,862,864,866,868,880,882,884,886,888,2000,2002,283,317,161,454,163,456,165,319,167,331,169,181,458,333,470,183,172,185,472,187,174,168,189,474,285,2001,476,301,478,303,335,305,180,490,337,2003,277,307,176,339,279,309,178,2004,287,351,321,353,182,2006,2008,2005,184,492,323,494,325,496,289,498,327,610,401,291,293,355,2007,190,357,192,359,194,2020,403,329,2009,612,186,614,341,616,343,618,345,630,2022,2024,2026,2028,2040,2042,2044,2046,2048,295,347,196,349,297,361,198,371,299,363,310,373,2060,2062,2064,2066,2068,2080,2082,2084,2086,411,365,312,375,413,367,314,377,632,369,316,379,415,381,417,383,391,385,318,405,393,387,395,389,330,2021,634,407,636,188,2023,638,409,2088,650,300,419,332,501,334,397,336,503,338,399,350,511,352,513,505,2025,652,302,654,507,656,304,658,509,2200,670,521,672,523,674,525,676,421,2027,678,527,690,306,692,2029,354,308,431,529,2041,356,320,694,423,358,322,696,698,425,810,541,2043,812,543,2045,2202,2047,2049,427,433,545,814,515,816,547,370,517,435,549,372,519,437,531,374,533,818,535,376,537,378,539,390,561,392,551,394,2204,2206,2208,2220,2222,2224,2226,2228,2240,2242,2244,553,439,563,451,555,453,565,2061,396,2246,324,455,326,2248,2260,2262,2264,2266,2268,2280,2282,2284,2286,2288,2400,2402,2404,2406,2408,2420,2422,2424,2426,2428,457,567,398,557,459,569,510,559,471,581,512,571,429,441,514,2440,2442,2444,2446,2448,2460,2462,2464,2466,2468,2480,573,473,328,830,575,475,340,832,834,477,583,516,836,479,585,838,577,491,579,493,591,850,593,852,595,495,597,854,599,856,858,443,2063,2065,2067,2069,2482,870,342,872,344,346,348,497,874,711,876,713,499,587,878,715,890,717,611,719,892,731,613,2081,2083,2085,894,589,896,445,447,449,898,701,461,463,2101,2103,2105,2100,2107,2109,2121,2123,2125,2102,2127,2129,2141,703,518,733,615,705,530,360,617,707,532,735,619,362,364,737,631,2087,2143,2145,2147,2149,2161,2163,2165,2167,2169,2181,2089,709,534,739,2201,633,721,536,751,465,467,538,723,469,481,550,753,552,755,2183,757,725,759,727,554,729,556,741,771,743,558,745,570,2185,2203,2205,2484,2187,2207,2209,2486,2189,2488,366,368,2104,773,635,747,637,749,639,775,651,761,653,763,655,777,657,765,2221,767,2301,2223,2225,2106,2303,2305,483,485,2307,2108,380,769,2120,2600,2602,2604,2606,2608,2620,2622,2624,2626,2628,2640,2642,2644,779,659,781,572,791,671,783,2227,574,793,673,785,576,2122,795,2124,2646,2648,2660,2662,2664,2666,2668,2680,2682,2684,2686,2688,2800,2309,675,787,578,797,677,789,590,901,487,489,592,799,601,603,594,911,679,903,691,913,2321,2323,2802,2804,2229,2806,2325,2327,915,905,596,382,2808,2820,2822,2824,2826,2828,2840,2842,2844,2846,2848,2860,2862,693,917,2329,598,2864,605,919,907,931,384,2866,695,909,2341,710,933,2126,2868,2880,2882,2884,2886,2888,4000,4002,4004,4006,4008,4020,4022,607,2343,2345,2347,2349,2128,2241,935,921,4024,2361,2363,2365,2367,2369,923,712,937,697,925,714,939,699,927,716,951,811,929,718,941,813,943,730,732,945,2381,2383,815,953,2140,2385,2387,817,955,2389,2501,2503,2505,2142,947,734,957,819,386,388,959,831,500,2507,736,971,833,502,504,973,835,949,738,975,750,977,752,979,754,991,756,4026,609,993,961,995,963,997,965,837,967,506,2144,2146,2509,2521,2523,2148,2160,2162,2525,2527,2529,2243,2164,2166,969,839,981,758,508,4028,851,999,2541,770,4040,621,853,983,772,985,855,520,623,2543,2168,2545,625,627,2245,2180,2182,2547,2549,2184,522,524,2561,2247,4042,4044,4046,4048,4060,4062,4064,4066,4068,4080,4082,4084,4086,4088,4200,526,857,987,774,989,859,1011,1013,1015,1017,1010,1012,1019,1031,1033,1014,4202,4204,4206,4208,4220,4222,4224,4226,4228,4240,4242,4244,4246,4248,4260,629,776,1016,1110,1018,2186,1112,1030,1114,1116,1118,1130,2188,1132,1032,1134,1136,528,2249,871,540,4262,873,1138,542,2261,875,1034,4264,1150,641,4266,877,778,544,2263,2300,2563,2565,2567,2302,2265,2267,2569,2581,2304,2306,2269,2308,4268,4280,4282,4284,4286,4288,4400,4402,4404,4406,4408,4420,4422,4424,4426,4428,2583,2585,2281,2587,643,4440,1036,1038,546,2589,2283,4442,548,645,2701,2320,2322,2703,4444,2705,2707,1111,2709,2721,4446,2723,2725,4448,2285,2287,4460,2727,879,2324,891,1035,1037,1039,1051,1053,1055,1057,1059,1071,1050,647,790,1152,560,4462,4464,4466,4468,4480,4482,4484,4486,4488,4600,4602,4604,4606,4608,4620,4622,4624,2729,893,1073,1075,562,564,1154,1156,1052,1158,1170,1172,2326,1174,1176,1178,1113,1190,1115,1077,1054,4626,649,1117,895,1192,1194,1079,1196,1119,1091,1198,1093,566,4628,4640,4642,4644,4646,4648,4660,4662,4664,4666,4668,4680,4682,4684,4686,4688,4800,4802,4804,4806,4808,4820,4822,4824,4826,4828,4840,4842,4844,4846,4848,4860,4862,4864,4866,4868,4880,4882,4884,4886,4888,6000,6002,6004,6006,6008,6020,6022,6024,6026,6028,6040,6042,6044,6046,6048,6060,6062,6064,6066,6068,6080,6082,6084,6086,6088,897,1095,1097,1099,1211,1213,1215,1217,1219,568,580,1310,1312,1314,1316,1318,1330,6200,6202,6204,6206,6208,6220,6222,6224,6226,6228,6240,6242,6244,6246,6248,6260,6262,6264,6266,1332,1334,1336,1338,1350,1352,2328,1354,661,899,1231,1233,1235,1237,1239,1251,582,6268,6280,6282,6284,6286,6288,6400,6402,6404,6406,6408,6420,6422,6424,6426,6428,6440,663,6442,2340,2741,2289,2401,2342,2344,2346,2348,584,665,2360,2403,2362,2364,2366,6444,6446,6448,6460,6462,6464,6466,6468,6480,6482,6484,6486,6488,6600,6602,6604,6606,6608,6620,6622,2405,2743,2407,2409,2421,2745,667,6624,586,2747,2423,2368,2749,2425,2380,2761,6626,6628,6640,6642,6644,6646,6648,6660,6662,6664,6666,6668,6680,6682,6684,6686,6688,6800,6802,669,2427,792,1356,1358,1370,1372,1374,1376,1378,2382,1390,588,2111,2113,2115,2384,6804,6806,6808,6820,6822,6824,6826,6828,6840,6842,6844,6846,6848,6860,6862,6864,6866,6868,6880,6882,6884,2117,2119,2131,2133,2135,2137,681,683,794,685,2139,2763,2151,2153,2765,2155,2157,6886,6888,8000,8002,8004,8006,8008,8020,8022,8024,8026,8028,8040,8042,8044,8046,8048,8060,8062,8064,700,2386,2767,2388,2500,2502,2769,2504,2506,687,689,2781,2429,2441,8066,2783,8068,8080,8082,8084,8086,8088,8200,8202,8204}

J’ai donné les termes de S et la succession des chiffres de S à Jos Leys afin qu’il voie si un travail d’animation est possible en images de synthèse. Merci à vous deux, les gars !

t={0,1,3,2,5,7,9,4,1,0,6,8,2,1,1,1,2,0,2,2,2,3,1,3,2,4,2,6,2,8,4,0,4,2,4,4,2,5,1,5,1,7,4,6,4,8,6,0,6,2,1,9,3,1,1,2,3,3,2,7,3,5,2,9,1,4,6,4,6,6,1,6,3,7,6,8,4,1,8,0,1,8,8,2,8,4,8,6,4,3,3,0,8,8,3,2,2,0,0,4,5,3,4,2,0,2,4,7,4,9,2,0,1,2,0,4,3,6,6,1,2,0,6,2,0,8,2,2,0,2,2,2,6,3,3,9,6,5,5,1,6,7,5,3,2,2,4,2,2,6,2,2,8,2,4,0,6,9,5,5,8,1,5,7,2,0,3,2,0,5,5,9,8,3,7,1,7,3,8,5,7,5,3,8,5,0,2,4,2,8,7,8,9,2,4,4,7,7,7,9,2,1,0,9,1,5,2,5,4,9,3,2,1,2,5,6,5,8,7,0,2,1,4,2,1,6,2,0,7,2,1,8,7,2,7,4,7,6,7,8,9,5,2,1,1,9,0,9,7,9,2,9,9,9,4,1,1,0,2,0,9,2,3,0,9,6,9,8,1,0,1,2,1,3,2,1,5,1,0,3,2,3,2,2,3,4,2,1,7,1,1,1,1,1,2,1,0,5,1,1,4,1,1,3,1,1,6,2,4,6,2,4,8,2,6,0,2,6,2,2,6,4,2,6,6,1,1,5,1,1,8,1,1,7,2,3,6,1,1,9,2,3,8,2,6,8,2,8,0,2,8,2,2,8,4,2,8,6,2,8,8,4,0,0,4,0,2,4,0,4,4,0,6,4,0,8,4,2,0,2,2,1,1,3,0,2,5,0,2,2,3,4,2,2,1,0,0,1,3,1,4,2,4,4,2,6,4,2,8,4,4,0,4,4,2,4,4,4,4,4,6,1,3,3,2,1,9,1,0,2,1,0,4,1,3,5,2,3,1,1,0,6,2,5,2,1,3,7,2,3,3,1,3,9,2,5,4,1,5,1,2,3,5,2,5,6,4,4,8,1,0,8,2,5,8,2,2,5,2,2,7,4,6,0,2,7,0,4,6,2,4,6,4,1,5,3,2,7,2,4,6,6,4,6,8,1,3,2,1,2,0,4,8,0,1,2,2,1,2,4,2,2,9,2,7,4,4,8,2,4,8,4,1,0,7,2,7,6,1,0,9,2,7,8,1,2,1,2,9,0,1,2,3,1,2,5,1,3,4,2,9,2,2,4,1,4,8,6,1,2,6,1,5,5,2,3,7,2,9,4,1,5,7,1,3,6,1,2,7,2,9,6,1,5,9,1,3,8,4,8,8,1,2,9,1,5,0,1,7,1,2,4,3,2,4,5,1,5,2,1,7,3,2,3,9,1,7,5,2,5,1,1,4,1,2,9,8,1,7,7,2,5,3,1,4,3,2,5,5,1,5,4,1,2,8,4,1,0,4,1,2,2,4,7,6,0,0,1,4,0,2,4,9,4,1,4,2,5,7,1,4,2,6,0,2,2,6,1,2,5,9,1,4,4,6,0,4,6,0,6,6,0,8,4,1,6,2,6,3,6,2,0,1,4,6,1,4,8,2,6,5,6,2,2,1,4,5,4,1,8,6,2,4,6,2,6,6,2,8,6,4,0,6,4,2,6,4,4,6,4,6,6,4,8,6,6,0,1,7,9,2,7,1,1,6,0,1,6,2,4,3,0,2,6,7,2,6,9,1,5,6,1,9,1,6,6,2,6,6,4,6,6,6,6,6,8,6,8,0,6,8,2,6,8,4,6,8,6,6,8,8,2,8,1,1,5,8,1,9,3,2,7,3,1,6,4,1,6,6,1,9,5,2,7,5,1,4,7,4,3,2,8,0,0,8,0,2,1,9,7,4,3,4,1,4,9,4,3,6,8,0,4,8,0,6,8,0,8,8,2,0,8,2,2,8,2,4,8,2,6,8,2,8,8,4,0,8,4,2,8,4,4,8,4,6,8,4,8,8,6,0,1,9,9,4,3,8,3,1,1,1,7,0,3,1,3,4,5,0,3,1,5,4,5,2,8,6,2,8,6,4,8,6,6,8,6,8,8,8,0,8,8,2,8,8,4,8,8,6,8,8,8,2,0,0,0,2,0,0,2,2,8,3,3,1,7,1,6,1,4,5,4,1,6,3,4,5,6,1,6,5,3,1,9,1,6,7,3,3,1,1,6,9,1,8,1,4,5,8,3,3,3,4,7,0,1,8,3,1,7,2,1,8,5,4,7,2,1,8,7,1,7,4,1,6,8,1,8,9,4,7,4,2,8,5,2,0,0,1,4,7,6,3,0,1,4,7,8,3,0,3,3,3,5,3,0,5,1,8,0,4,9,0,3,3,7,2,0,0,3,2,7,7,3,0,7,1,7,6,3,3,9,2,7,9,3,0,9,1,7,8,2,0,0,4,2,8,7,3,5,1,3,2,1,3,5,3,1,8,2,2,0,0,6,2,0,0,8,2,0,0,5,1,8,4,4,9,2,3,2,3,4,9,4,3,2,5,4,9,6,2,8,9,4,9,8,3,2,7,6,1,0,4,0,1,2,9,1,2,9,3,3,5,5,2,0,0,7,1,9,0,3,5,7,1,9,2,3,5,9,1,9,4,2,0,2,0,4,0,3,3,2,9,2,0,0,9,6,1,2,1,8,6,6,1,4,3,4,1,6,1,6,3,4,3,6,1,8,3,4,5,6,3,0,2,0,2,2,2,0,2,4,2,0,2,6,2,0,2,8,2,0,4,0,2,0,4,2,2,0,4,4,2,0,4,6,2,0,4,8,2,9,5,3,4,7,1,9,6,3,4,9,2,9,7,3,6,1,1,9,8,3,7,1,2,9,9,3,6,3,3,1,0,3,7,3,2,0,6,0,2,0,6,2,2,0,6,4,2,0,6,6,2,0,6,8,2,0,8,0,2,0,8,2,2,0,8,4,2,0,8,6,4,1,1,3,6,5,3,1,2,3,7,5,4,1,3,3,6,7,3,1,4,3,7,7,6,3,2,3,6,9,3,1,6,3,7,9,4,1,5,3,8,1,4,1,7,3,8,3,3,9,1,3,8,5,3,1,8,4,0,5,3,9,3,3,8,7,3,9,5,3,8,9,3,3,0,2,0,2,1,6,3,4,4,0,7,6,3,6,1,8,8,2,0,2,3,6,3,8,4,0,9,2,0,8,8,6,5,0,3,0,0,4,1,9,3,3,2,5,0,1,3,3,4,3,9,7,3,3,6,5,0,3,3,3,8,3,9,9,3,5,0,5,1,1,3,5,2,5,1,3,5,0,5,2,0,2,5,6,5,2,3,0,2,6,5,4,5,0,7,6,5,6,3,0,4,6,5,8,5,0,9,2,2,0,0,6,7,0,5,2,1,6,7,2,5,2,3,6,7,4,5,2,5,6,7,6,4,2,1,2,0,2,7,6,7,8,5,2,7,6,9,0,3,0,6,6,9,2,2,0,2,9,3,5,4,3,0,8,4,3,1,5,2,9,2,0,4,1,3,5,6,3,2,0,6,9,4,4,2,3,3,5,8,3,2,2,6,9,6,6,9,8,4,2,5,8,1,0,5,4,1,2,0,4,3,8,1,2,5,4,3,2,0,4,5,2,2,0,2,2,0,4,7,2,0,4,9,4,2,7,4,3,3,5,4,5,8,1,4,5,1,5,8,1,6,5,4,7,3,7,0,5,1,7,4,3,5,5,4,9,3,7,2,5,1,9,4,3,7,5,3,1,3,7,4,5,3,3,8,1,8,5,3,5,3,7,6,5,3,7,3,7,8,5,3,9,3,9,0,5,6,1,3,9,2,5,5,1,3,9,4,2,2,0,4,2,2,0,6,2,2,0,8,2,2,2,0,2,2,2,2,2,2,2,4,2,2,2,6,2,2,2,8,2,2,4,0,2,2,4,2,2,2,4,4,5,5,3,4,3,9,5,6,3,4,5,1,5,5,5,4,5,3,5,6,5,2,0,6,1,3,9,6,2,2,4,6,3,2,4,4,5,5,3,2,6,2,2,4,8,2,2,6,0,2,2,6,2,2,2,6,4,2,2,6,6,2,2,6,8,2,2,8,0,2,2,8,2,2,2,8,4,2,2,8,6,2,2,8,8,2,4,0,0,2,4,0,2,2,4,0,4,2,4,0,6,2,4,0,8,2,4,2,0,2,4,2,2,2,4,2,4,2,4,2,6,2,4,2,8,4,5,7,5,6,7,3,9,8,5,5,7,4,5,9,5,6,9,5,1,0,5,5,9,4,7,1,5,8,1,5,1,2,5,7,1,4,2,9,4,4,1,5,1,4,2,4,4,0,2,4,4,2,2,4,4,4,2,4,4,6,2,4,4,8,2,4,6,0,2,4,6,2,2,4,6,4,2,4,6,6,2,4,6,8,2,4,8,0,5,7,3,4,7,3,3,2,8,8,3,0,5,7,5,4,7,5,3,4,0,8,3,2,8,3,4,4,7,7,5,8,3,5,1,6,8,3,6,4,7,9,5,8,5,8,3,8,5,7,7,4,9,1,5,7,9,4,9,3,5,9,1,8,5,0,5,9,3,8,5,2,5,9,5,4,9,5,5,9,7,8,5,4,5,9,9,8,5,6,8,5,8,4,4,3,2,0,6,3,2,0,6,5,2,0,6,7,2,0,6,9,2,4,8,2,8,7,0,3,4,2,8,7,2,3,4,4,3,4,6,3,4,8,4,9,7,8,7,4,7,1,1,8,7,6,7,1,3,4,9,9,5,8,7,8,7,8,7,1,5,8,9,0,7,1,7,6,1,1,7,1,9,8,9,2,7,3,1,6,1,3,2,0,8,1,2,0,8,3,2,0,8,5,8,9,4,5,8,9,8,9,6,4,4,5,4,4,7,4,4,9,8,9,8,7,0,1,4,6,1,4,6,3,2,1,0,1,2,1,0,3,2,1,0,5,2,1,0,0,2,1,0,7,2,1,0,9,2,1,2,1,2,1,2,3,2,1,2,5,2,1,0,2,2,1,2,7,2,1,2,9,2,1,4,1,7,0,3,5,1,8,7,3,3,6,1,5,7,0,5,5,3,0,3,6,0,6,1,7,7,0,7,5,3,2,7,3,5,6,1,9,3,6,2,3,6,4,7,3,7,6,3,1,2,0,8,7,2,1,4,3,2,1,4,5,2,1,4,7,2,1,4,9,2,1,6,1,2,1,6,3,2,1,6,5,2,1,6,7,2,1,6,9,2,1,8,1,2,0,8,9,7,0,9,5,3,4,7,3,9,2,2,0,1,6,3,3,7,2,1,5,3,6,7,5,1,4,6,5,4,6,7,5,3,8,7,2,3,4,6,9,4,8,1,5,5,0,7,5,3,5,5,2,7,5,5,2,1,8,3,7,5,7,7,2,5,7,5,9,7,2,7,5,5,4,7,2,9,5,5,6,7,4,1,7,7,1,7,4,3,5,5,8,7,4,5,5,7,0,2,1,8,5,2,2,0,3,2,2,0,5,2,4,8,4,2,1,8,7,2,2,0,7,2,2,0,9,2,4,8,6,2,1,8,9,2,4,8,8,3,6,6,3,6,8,2,1,0,4,7,7,3,6,3,5,7,4,7,6,3,7,7,4,9,6,3,9,7,7,5,6,5,1,7,6,1,6,5,3,7,6,3,6,5,5,7,7,7,6,5,7,7,6,5,2,2,2,1,7,6,7,2,3,0,1,2,2,2,3,2,2,2,5,2,1,0,6,2,3,0,3,2,3,0,5,4,8,3,4,8,5,2,3,0,7,2,1,0,8,3,8,0,7,6,9,2,1,2,0,2,6,0,0,2,6,0,2,2,6,0,4,2,6,0,6,2,6,0,8,2,6,2,0,2,6,2,2,2,6,2,4,2,6,2,6,2,6,2,8,2,6,4,0,2,6,4,2,2,6,4,4,7,7,9,6,5,9,7,8,1,5,7,2,7,9,1,6,7,1,7,8,3,2,2,2,7,5,7,4,7,9,3,6,7,3,7,8,5,5,7,6,2,1,2,2,7,9,5,2,1,2,4,2,6,4,6,2,6,4,8,2,6,6,0,2,6,6,2,2,6,6,4,2,6,6,6,2,6,6,8,2,6,8,0,2,6,8,2,2,6,8,4,2,6,8,6,2,6,8,8,2,8,0,0,2,3,0,9,6,7,5,7,8,7,5,7,8,7,9,7,6,7,7,7,8,9,5,9,0,9,0,1,4,8,7,4,8,9,5,9,2,7,9,9,6,0,1,6,0,3,5,9,4,9,1,1,6,7,9,9,0,3,6,9,1,9,1,3,2,3,2,1,2,3,2,3,2,8,0,2,2,8,0,4,2,2,2,9,2,8,0,6,2,3,2,5,2,3,2,7,9,1,5,9,0,5,5,9,6,3,8,2,2,8,0,8,2,8,2,0,2,8,2,2,2,8,2,4,2,8,2,6,2,8,2,8,2,8,4,0,2,8,4,2,2,8,4,4,2,8,4,6,2,8,4,8,2,8,6,0,2,8,6,2,6,9,3,9,1,7,2,3,2,9,5,9,8,2,8,6,4,6,0,5,9,1,9,9,0,7,9,3,1,3,8,4,2,8,6,6,6,9,5,9,0,9,2,3,4,1,7,1,0,9,3,3,2,1,2,6,2,8,6,8,2,8,8,0,2,8,8,2,2,8,8,4,2,8,8,6,2,8,8,8,4,0,0,0,4,0,0,2,4,0,0,4,4,0,0,6,4,0,0,8,4,0,2,0,4,0,2,2,6,0,7,2,3,4,3,2,3,4,5,2,3,4,7,2,3,4,9,2,1,2,8,2,2,4,1,9,3,5,9,2,1,4,0,2,4,2,3,6,1,2,3,6,3,2,3,6,5,2,3,6,7,2,3,6,9,9,2,3,7,1,2,9,3,7,6,9,7,9,2,5,7,1,4,9,3,9,6,9,9,9,2,7,7,1,6,9,5,1,8,1,1,9,2,9,7,1,8,9,4,1,8,1,3,9,4,3,7,3,0,7,3,2,9,4,5,2,3,8,1,2,3,8,3,8,1,5,9,5,3,2,1,4,0,2,3,8,5,2,3,8,7,8,1,7,9,5,5,2,3,8,9,2,5,0,1,2,5,0,3,2,5,0,5,2,1,4,2,9,4,7,7,3,4,9,5,7,8,1,9,3,8,6,3,8,8,9,5,9,8,3,1,5,0,0,2,5,0,7,7,3,6,9,7,1,8,3,3,5,0,2,5,0,4,9,7,3,8,3,5,9,4,9,7,3,8,9,7,5,7,5,0,9,7,7,7,5,2,9,7,9,7,5,4,9,9,1,7,5,6,4,0,2,6,6,0,9,9,9,3,9,6,1,9,9,5,9,6,3,9,9,7,9,6,5,8,3,7,9,6,7,5,0,6,2,1,4,4,2,1,4,6,2,5,0,9,2,5,2,1,2,5,2,3,2,1,4,8,2,1,6,0,2,1,6,2,2,5,2,5,2,5,2,7,2,5,2,9,2,2,4,3,2,1,6,4,2,1,6,6,9,6,9,8,3,9,9,8,1,7,5,8,5,0,8,4,0,2,8,8,5,1,9,9,9,2,5,4,1,7,7,0,4,0,4,0,6,2,1,8,5,3,9,8,3,7,7,2,9,8,5,8,5,5,5,2,0,6,2,3,2,5,4,3,2,1,6,8,2,5,4,5,6,2,5,6,2,7,2,2,4,5,2,1,8,0,2,1,8,2,2,5,4,7,2,5,4,9,2,1,8,4,5,2,2,5,2,4,2,5,6,1,2,2,4,7,4,0,4,2,4,0,4,4,4,0,4,6,4,0,4,8,4,0,6,0,4,0,6,2,4,0,6,4,4,0,6,6,4,0,6,8,4,0,8,0,4,0,8,2,4,0,8,4,4,0,8,6,4,0,8,8,4,2,0,0,5,2,6,8,5,7,9,8,7,7,7,4,9,8,9,8,5,9,1,0,1,1,1,0,1,3,1,0,1,5,1,0,1,7,1,0,1,0,1,0,1,2,1,0,1,9,1,0,3,1,1,0,3,3,1,0,1,4,4,2,0,2,4,2,0,4,4,2,0,6,4,2,0,8,4,2,2,0,4,2,2,2,4,2,2,4,4,2,2,6,4,2,2,8,4,2,4,0,4,2,4,2,4,2,4,4,4,2,4,6,4,2,4,8,4,2,6,0,6,2,9,7,7,6,1,0,1,6,1,1,1,0,1,0,1,8,2,1,8,6,1,1,1,2,1,0,3,0,1,1,1,4,1,1,1,6,1,1,1,8,1,1,3,0,2,1,8,8,1,1,3,2,1,0,3,2,1,1,3,4,1,1,3,6,5,2,8,2,2,4,9,8,7,1,5,4,0,4,2,6,2,8,7,3,1,1,3,8,5,4,2,2,2,6,1,8,7,5,1,0,3,4,4,2,6,4,1,1,5,0,6,4,1,4,2,6,6,8,7,7,7,7,8,5,4,4,2,2,6,3,2,3,0,0,2,5,6,3,2,5,6,5,2,5,6,7,2,3,0,2,2,2,6,5,2,2,6,7,2,5,6,9,2,5,8,1,2,3,0,4,2,3,0,6,2,2,6,9,2,3,0,8,4,2,6,8,4,2,8,0,4,2,8,2,4,2,8,4,4,2,8,6,4,2,8,8,4,4,0,0,4,4,0,2,4,4,0,4,4,4,0,6,4,4,0,8,4,4,2,0,4,4,2,2,4,4,2,4,4,4,2,6,4,4,2,8,2,5,8,3,2,5,8,5,2,2,8,1,2,5,8,7,6,4,3,4,4,4,0,1,0,3,6,1,0,3,8,5,4,6,2,5,8,9,2,2,8,3,4,4,4,2,5,4,8,6,4,5,2,7,0,1,2,3,2,0,2,3,2,2,2,7,0,3,4,4,4,4,2,7,0,5,2,7,0,7,1,1,1,1,2,7,0,9,2,7,2,1,4,4,4,6,2,7,2,3,2,7,2,5,4,4,4,8,2,2,8,5,2,2,8,7,4,4,6,0,2,7,2,7,8,7,9,2,3,2,4,8,9,1,1,0,3,5,1,0,3,7,1,0,3,9,1,0,5,1,1,0,5,3,1,0,5,5,1,0,5,7,1,0,5,9,1,0,7,1,1,0,5,0,6,4,7,7,9,0,1,1,5,2,5,6,0,4,4,6,2,4,4,6,4,4,4,6,6,4,4,6,8,4,4,8,0,4,4,8,2,4,4,8,4,4,4,8,6,4,4,8,8,4,6,0,0,4,6,0,2,4,6,0,4,4,6,0,6,4,6,0,8,4,6,2,0,4,6,2,2,4,6,2,4,2,7,2,9,8,9,3,1,0,7,3,1,0,7,5,5,6,2,5,6,4,1,1,5,4,1,1,5,6,1,0,5,2,1,1,5,8,1,1,7,0,1,1,7,2,2,3,2,6,1,1,7,4,1,1,7,6,1,1,7,8,1,1,1,3,1,1,9,0,1,1,1,5,1,0,7,7,1,0,5,4,4,6,2,6,6,4,9,1,1,1,7,8,9,5,1,1,9,2,1,1,9,4,1,0,7,9,1,1,9,6,1,1,1,9,1,0,9,1,1,1,9,8,1,0,9,3,5,6,6,4,6,2,8,4,6,4,0,4,6,4,2,4,6,4,4,4,6,4,6,4,6,4,8,4,6,6,0,4,6,6,2,4,6,6,4,4,6,6,6,4,6,6,8,4,6,8,0,4,6,8,2,4,6,8,4,4,6,8,6,4,6,8,8,4,8,0,0,4,8,0,2,4,8,0,4,4,8,0,6,4,8,0,8,4,8,2,0,4,8,2,2,4,8,2,4,4,8,2,6,4,8,2,8,4,8,4,0,4,8,4,2,4,8,4,4,4,8,4,6,4,8,4,8,4,8,6,0,4,8,6,2,4,8,6,4,4,8,6,6,4,8,6,8,4,8,8,0,4,8,8,2,4,8,8,4,4,8,8,6,4,8,8,8,6,0,0,0,6,0,0,2,6,0,0,4,6,0,0,6,6,0,0,8,6,0,2,0,6,0,2,2,6,0,2,4,6,0,2,6,6,0,2,8,6,0,4,0,6,0,4,2,6,0,4,4,6,0,4,6,6,0,4,8,6,0,6,0,6,0,6,2,6,0,6,4,6,0,6,6,6,0,6,8,6,0,8,0,6,0,8,2,6,0,8,4,6,0,8,6,6,0,8,8,8,9,7,1,0,9,5,1,0,9,7,1,0,9,9,1,2,1,1,1,2,1,3,1,2,1,5,1,2,1,7,1,2,1,9,5,6,8,5,8,0,1,3,1,0,1,3,1,2,1,3,1,4,1,3,1,6,1,3,1,8,1,3,3,0,6,2,0,0,6,2,0,2,6,2,0,4,6,2,0,6,6,2,0,8,6,2,2,0,6,2,2,2,6,2,2,4,6,2,2,6,6,2,2,8,6,2,4,0,6,2,4,2,6,2,4,4,6,2,4,6,6,2,4,8,6,2,6,0,6,2,6,2,6,2,6,4,6,2,6,6,1,3,3,2,1,3,3,4,1,3,3,6,1,3,3,8,1,3,5,0,1,3,5,2,2,3,2,8,1,3,5,4,6,6,1,8,9,9,1,2,3,1,1,2,3,3,1,2,3,5,1,2,3,7,1,2,3,9,1,2,5,1,5,8,2,6,2,6,8,6,2,8,0,6,2,8,2,6,2,8,4,6,2,8,6,6,2,8,8,6,4,0,0,6,4,0,2,6,4,0,4,6,4,0,6,6,4,0,8,6,4,2,0,6,4,2,2,6,4,2,4,6,4,2,6,6,4,2,8,6,4,4,0,6,6,3,6,4,4,2,2,3,4,0,2,7,4,1,2,2,8,9,2,4,0,1,2,3,4,2,2,3,4,4,2,3,4,6,2,3,4,8,5,8,4,6,6,5,2,3,6,0,2,4,0,3,2,3,6,2,2,3,6,4,2,3,6,6,6,4,4,4,6,4,4,6,6,4,4,8,6,4,6,0,6,4,6,2,6,4,6,4,6,4,6,6,6,4,6,8,6,4,8,0,6,4,8,2,6,4,8,4,6,4,8,6,6,4,8,8,6,6,0,0,6,6,0,2,6,6,0,4,6,6,0,6,6,6,0,8,6,6,2,0,6,6,2,2,2,4,0,5,2,7,4,3,2,4,0,7,2,4,0,9,2,4,2,1,2,7,4,5,6,6,7,6,6,2,4,5,8,6,2,7,4,7,2,4,2,3,2,3,6,8,2,7,4,9,2,4,2,5,2,3,8,0,2,7,6,1,6,6,2,6,6,6,2,8,6,6,4,0,6,6,4,2,6,6,4,4,6,6,4,6,6,6,4,8,6,6,6,0,6,6,6,2,6,6,6,4,6,6,6,6,6,6,6,8,6,6,8,0,6,6,8,2,6,6,8,4,6,6,8,6,6,6,8,8,6,8,0,0,6,8,0,2,6,6,9,2,4,2,7,7,9,2,1,3,5,6,1,3,5,8,1,3,7,0,1,3,7,2,1,3,7,4,1,3,7,6,1,3,7,8,2,3,8,2,1,3,9,0,5,8,8,2,1,1,1,2,1,1,3,2,1,1,5,2,3,8,4,6,8,0,4,6,8,0,6,6,8,0,8,6,8,2,0,6,8,2,2,6,8,2,4,6,8,2,6,6,8,2,8,6,8,4,0,6,8,4,2,6,8,4,4,6,8,4,6,6,8,4,8,6,8,6,0,6,8,6,2,6,8,6,4,6,8,6,6,6,8,6,8,6,8,8,0,6,8,8,2,6,8,8,4,2,1,1,7,2,1,1,9,2,1,3,1,2,1,3,3,2,1,3,5,2,1,3,7,6,8,1,6,8,3,7,9,4,6,8,5,2,1,3,9,2,7,6,3,2,1,5,1,2,1,5,3,2,7,6,5,2,1,5,5,2,1,5,7,6,8,8,6,6,8,8,8,8,0,0,0,8,0,0,2,8,0,0,4,8,0,0,6,8,0,0,8,8,0,2,0,8,0,2,2,8,0,2,4,8,0,2,6,8,0,2,8,8,0,4,0,8,0,4,2,8,0,4,4,8,0,4,6,8,0,4,8,8,0,6,0,8,0,6,2,8,0,6,4,7,0,0,2,3,8,6,2,7,6,7,2,3,8,8,2,5,0,0,2,5,0,2,2,7,6,9,2,5,0,4,2,5,0,6,6,8,7,6,8,9,2,7,8,1,2,4,2,9,2,4,4,1,8,0,6,6,2,7,8,3,8,0,6,8,8,0,8,0,8,0,8,2,8,0,8,4,8,0,8,6,8,0,8,8,8,2,0,0,8,2,0,2,8,2,0,4,}