I am currently learning about the Legendre's formula. Thus far, I was able to solve the algorithm with the following approach:
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)); // 312
However, I just couldn't quite get over the hump recursively. This is what I have so far:
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)); // 300
As you can see, most of the results are incorrect. Am I on the right track? Can someone kindly point me in the right direction or show me what I'm doing wrong? Any feedback will be greatly appreciated. Million thanks in advance :)
I started by converting your first code into a normal function:
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)); // 312and converted that into a recursive function:
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)); // 312and that can be made into a oneliner like this:
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)); // 312I haven't studied this algorithm and these answers are just based off your first code snippet and your test cases.