Actualmente estoy aprendiendo sobre la fórmula de Legendre. Hasta ahora, pude resolver el algoritmo con el siguiente enfoque:
const legendre = (p,n,res=0) => Array.from({length:n},(_,i) => res+=Math.floor(n/p**++i)) && res; console.log(legendre(5,90)); // 21 console.log(legendre(2,130)); // 128 console.log(legendre(3,60)); // 28 console.log(legendre(9,5)); // 0 console.log(legendre(5,1250)); // 312Sin embargo, simplemente no pude superar la joroba recursivamente. Esto es lo que tengo hasta ahora:
const legendre = (p,n,i=1,res=0) => p > n ? res : res + legendre(p**i,n,i+1,Math.floor(n/p**i)) console.log(legendre(5,90)); // 21 console.log(legendre(2,130)); // 99 console.log(legendre(3,60)); // 26 console.log(legendre(9,5)); // 0 console.log(legendre(5,1250)); // 300Como puede ver, la mayoría de los resultados son incorrectos. ¿Estoy en el camino correcto? ¿Puede alguien amablemente indicarme la dirección correcta o mostrarme qué estoy haciendo mal? Cualquier comentario será muy apreciado. Millones de gracias de antemano :)
Empecé convirtiendo tu primer código en una función normal:
const legendre = (p, n) => { let res = 0; for (let i = 1; i <= n; i++) { res += Math.floor(n/p**i); } return res; } console.log(legendre(5,90)); // 21 console.log(legendre(2,130)); // 128 console.log(legendre(3,60)); // 28 console.log(legendre(9,5)); // 0 console.log(legendre(5,1250)); // 312y convertido eso en una función recursiva:
const legendre = (p, n, i=1, res=0) => { // base case -> done if (i > n) return res + Math.floor(n/p**i); return legendre(p, n, i+1, res + Math.floor(n/p**i)); } console.log(legendre(5,90)); // 21 console.log(legendre(2,130)); // 128 console.log(legendre(3,60)); // 28 console.log(legendre(9,5)); // 0 console.log(legendre(5,1250)); // 312y eso se puede convertir en un oneliner como este:
const legendre = (p,n,i=1,res=0) => i > n ? res + Math.floor(n/p**i) : legendre(p,n,i+1,res +Math.floor(n/p**i)) console.log(legendre(5,90)); // 21 console.log(legendre(2,130)); // 128 console.log(legendre(3,60)); // 28 console.log(legendre(9,5)); // 0 console.log(legendre(5,1250)); // 312No he estudiado este algoritmo y estas respuestas solo se basan en su primer fragmento de código y sus casos de prueba.