Find the sum of the largest odd divisors using PHP

This article introduces how to find the sum of the largest odd divisors using PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

Xiao Yi is a number theory enthusiast and is very interested in the odd divisors of a number. One day Xiaoyi encountered such a problem: Define the function f(x) as the largest odd divisor of x, and x is a positive integer. For example: f(44) = 11.

Now given an N, we need to find f(1) f(2) f(3)…….f(N)

For example : N = 7

f(1) f(2) f(3) f(4) f(5) f(6) f(7) = 1 1 3 1 5 3 7 = 21

Xiaoyi has encountered difficulties in calculating this problem and needs you to design an algorithm to help him.

<?php
$num = trim(fgets(STDIN));

function jNum($num){
        $m = $num/2;
        $res = 1;
        if($num&0x1 == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身
                $res = $num;
                goto HELL;
        }
        for($i = 1; $i<=$m; $i=$i+2){//如果不是，那么就从1开始一直往上除，每次+2（奇数）
                if($num%$i==0){
                        $res = $i;
                }
        }
        HELL:
        return $res;
}

function jNum2($num)
{
        $res = 0;

        for($i=1;$i<=$num;$i++){
                if(($i&0x1) == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身
                        $res+=$i;
                }else{
                        $n = $i;
                        while(true){//优化，从最大的数开始往下除
                                $n = $n>>1;
                                if(($n&0x1) == 1){
                                        $res+=$n;
                                        break;
                                }
                        }
                }
        }

        HELL:
        return $res;
}

function jNum3($num){//公式法
        if($num == 1){
                return 1;
        }
        if(($num&0x1) == 0){
                return jNum3($num>>1)+$num*$num/4;
        }else{
                return jNum3($num-1)+$num;
        }

}
//$sum = 0;
//for($i = 1; $i<=$num; $i++){
//      $sum+=jNum($i);
//}
//echo $sum;

//echo jNum2($num);

echo jNum3($num);

Start with the conventional thinking. Method 1, which has been debugged, always times out. If you change it to method 2, it still times out. There is no essential difference.

Change your thinking. .

In the process of finding sum(i), if i is an odd number, it can be found directly, which is i itself, that is, f(i) = i.

The problem is to find the sum of all f(i), i is an even number.

Because it is the largest odd divisor, so f(2k) = f(k), so f(2) f(4) … f(2k) = f(1) f(2) … f( k);

Therefore, it is not easy to think of a general formula that can be obtained by mathematical induction

. . . Such a BT question. .

This article is reproduced from: https://blog.csdn.net/qq_28602957/article/details/77914402

Recommended learning: PHP video tutorial

The above is the detailed content of Find the sum of the largest odd divisors using PHP. For more information, please follow other related articles on the PHP Chinese website!