Somme de produits avec PGCD
Le cadre
Pour \(n\in\mathbb N^*\), on considère la somme suivante :
\[s_n = \sum_{i=1}^{n} i × \textrm{PGCD}(n, i)\]
Exemples
\[s_4 = 1× \textrm{PGCD}(4, 1) + 2 × \textrm{PGCD}(4, 2) + 3 × \textrm{PGCD}(4, 3) + 4 × \textrm{PGCD}(4, 4)\]
Cette somme est égale à \(1×1 + 2×2 + 3×1 + 4×4\) donc \(s_4=24\).
\[s_5 = 1× \textrm{PGCD}(5, 1) + 2 × \textrm{PGCD}(5, 2) + 3 × \textrm{PGCD}(5, 3) + 4 × \textrm{PGCD}(5, 4) + 5 × \textrm{PGCD}(5, 5)\]
Cette somme est égale à \(1×1 + 2×1 + 3×1 + 4×1 + 5×5\) donc \(s_5 = 35\).
\[s_6 = 1× \textrm{PGCD}(6, 1) + 2 × \textrm{PGCD}(6, 2) + 3 × \textrm{PGCD}(6, 3) + 4 × \textrm{PGCD}(6, 4) + 5 × \textrm{PGCD}(6, 5) + 6 × \textrm{PGCD}(6, 6)\]
Cette somme est égale à \(1×1 + 2×2 + 3×3 + 4×2 + 5×1 + 6×6\) donc \(s_6 = 63\).
Exercice
Coder une fonction somme_produit_pgcd qui prend en paramètre un entier naturel non nul n et qui renvoie la somme \(s_n\) considérée au-dessus.
On pourra se contenter d'une complexité pseudo-linéaire 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)*vd4613k×RmhtsP(S0à+2CDi: 050C0s0M0r0X0q0N0l0v0q0r0N0N0o010M0X0u010406050N0y0K0K0r0i0p040Q0n0q0y0?0n0j050e0}0 11130{0u04051j1c1m0e1j0{0C0X0B0+0-0/0;0L0X0x0L0q1A0L0M0_050$0k0q0s1v0.0:011z1B1D1B0M1J1L1H0M0i1k0M0L1N1x010f0(0s0j0r0K0s010+160N0u0r0j0;0U1H1^1`1(1P1+1L1.1:0_0a0l0O0i0n0u0n0N0X190j0l0!1?0i0i0s0v2h1c1 0j1k0e1$2u1Z1#1!1I0C210;1D0j1-2e1H1s1u0,1O2E0X2G0j0n2K1H0u2n1k2s2u2Y0|1_2i2M1)2R0i100q0_0l0F2r2$0`2#202(1P2*2,2.0U2;1`2?2s2D012{0r2-040l0G2 2t0{322_0;35370l0D3b312$333h2.0c3l3d3n3f340n2+362.0E3s2@2%1w2`3x2|380g3C3e3F3g3H3z380h3L3u3N3w3y3i0d3T2^3V3p040F0R3!3E2N3W3I0F2:1d2=1n2W1c2K2x0C1#2C3v0v2S1;1k3`1l3^2!3=3005400!2X3U3-0H0j0_0f2b0K3l3D330w2.4m3M3-0j4h04101$4r4e1)4p384z3#4f4v0X0K2d0i0M3l0l4n3v4v0x0v0C3s3t4F1)0H0_0!0f4E3,4B4q482t4P3$0f0_0N0n0 0s0m2V2S0y2g4^4S4U4+4d4X1P0^040P4%3o0_1b504-3-540z0Y3+4o2.0l5k573v0N0C0_015r5h5n5p385k0l0J1-0B0n0X1M0-0l4;4?0l2d0y0i0l0X0l360-0j0M2j1M0F0l0S0l5a2Y4W4(1P5o5j5k0!0*4_0C4{0M0*5O0I290t0V0W0P0j0b5N0z5t3V5)5w5k5r013s5x4O4s2)4:0m5!2=6a4A1P0n0_0o4N5c1)0K0X0_3*5006696o1P4Z040f3x6n6b2`0_0X6D6i0;0n4C2P6I523g0k0_0i1`0x0s5m3V54565b6E0;6q0_3;2!6$01540b6O5%3g596:336k040T6@3v6(3(6X5d0_5f68695x6x6=040N6e6|3V6_0T6m506h6P346G7c3-6_0A7m6c044~701)6Z7u6F046f496,6.7q7y6H6#6J6-72745l6,6z2n0M5L7A2t7i6;7k797b6u1c4b0s2u2V7$3_1t3{2x2A2v0r1K7)0e3`0{7?0#0%0)04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)