Somme de sommes de PGCD
Le cadre
Pour \(n\in\mathbb N^*\), on considère la somme suivante :
\[t_n = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \textrm{PGCD}(i, j)\]
Exemples
\(t_1 = 0\)
(La somme est vide)
\(t_2 = \textrm{PGCD}(1, 2)\)
\(t_2 = 1\)
\(t_3 = \textrm{PGCD}(1, 2) + \textrm{PGCD}(1, 3) + \textrm{PGCD}(2, 3)\)
\(t_3 = 1+1+1 = 3\)
\(t_4 = \textrm{PGCD}(1, 2) + \textrm{PGCD}(1, 3) + \textrm{PGCD}(1, 4) + \textrm{PGCD}(2, 3) + \textrm{PGCD}(2, 4) + \textrm{PGCD}(3, 4)\)
\(t_4= 1+1+1+1+2+1 = 7\)
Exercice
Coder une fonction somme_somme_pgcd qui prend en paramètre un entier naturel non nul n et qui renvoie la somme \(t_n\) considérée au-dessus.
On pourra se contenter d'une complexité pseudo-quadratique en n.
On pourra importer la fonction gcd depuis le module math
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 ,59/f78rnb _o=ylaeGpcwgu)vd4613kRmhtsP(S0à+2CjDi: 050B0s0K0r0W0q0L0l0v0q0r0L0L0o010K0W0u010406050L0y0I0I0r0i0p040O0n0q0y0=0n0j050e0|0~10120`0u04051i1b1l0e1i0`0B0W0A0*0,0.0:0J0W0x0J0q1z0J0K0^050#0k0q0s1u0-0/011y1A1C1A0K1I1K1G0K0i1j0K0J1M1w010f0%0s0j0r0I0s010*150L0u0r0j0:0S1G1@1_1%1O1*1K1-1/0^0a0l0M0i0n0u0n0L0W180j0l0Z1=0i0i0s0v2g1b1~0j1j0e1#2t1Y1!1Z1H0B200:1C0j1,2d1G1r1t0+1N2D0W2F0j0n2J1G0u2m1j2r2t2X0{1^2h2L1(2Q0i0 0q0^0l0E2q2#0_2!1 2%1O2)2+2-0S2:1_2=2r2C012`0r2,040l0F2~2s0`312^0:34360l0C3a302#323g2-0c3k3c3m3e330n2*352-0D3r2?2$1v2_3w2{370g3B3d3E3f3G3y370h3K3t3M3v3x3h0d3S2@3U3o040E0P3Z3D2M3V3H0E2/1c2;3s3!3,3$0E2}3;2 3?3+2(3O360E393|2s1m2V1b2J2w0B1!2B3u0v2R1:1j4a1k482Z451j4g0Z2W3T3,0G0j0^0f2a0I3k3C320w2-4B3L3^4w040 1#4G4t1(4E374N3@1(4v0^0W0I2c0i0K3k0l4C3u4J0x0v0B3r3~320G0^0Z0f4S3 1O4Q4%4o4(3#0f0^0L0n0~0s0m52540m0u4+4-4}4H1(0@040N4^3n0^1a5d4O1O5g0z0X3*4D2-0l5w5j3u0L0B0^015D5t5z5B375w0l0H1,0A0n0W1L0,0l571/0l2c0y0i0l0W0l350,0j0K2i1L0E0l0Q0l5m2X4/5G5v5J5J2j5R5T1L5W5Y0U5#0q5%5)2j5!0R2.5-5/5F3U5A5@5^6f2j0M0t0T0V0N0W0b0l0U0z6b3,6d5I5w5D013r5^4~3^0^0K0m5:2;4%5e1O0n0^0o4$6B1(0I0W0^3)4o066A6J0:4;040f3w6O6Y334W6(5o0:0n4Q2O6,4T2_0k0^0i1_0x0s5y3U5g5i5n6?0:6R0^3:2Z6)5g0b6=4_3f5l7c326L040R7g3u753%6~3,5q5s6V6f5J6P1O6!6$0i7l3#0^0U7B3,6/4W6G2 6I6-336^046`0j6|7p5f0^71787M4J0W7F1(7i7k4o7L73017n772;7w0:7a7#2_7f7)7:017%7?746S7o727d017r6z7u6f7`4J6E7J2s7*827%6N7_6)4*4,7T5p7V8l7e047!81327=8h7Y7D8o830^6r7t7v6)6!2m0K5X8b4R8i6D6F3B0e4q0s2t2U8R491s4b2w2z2u0r1J8U0e4a0`8(0!0$0(04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)