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 :)

CodePudding user response：

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)); // 312

and 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)); // 312

and 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)); // 312

I haven't studied this algorithm and these answers are just based off your first code snippet and your test cases.