题目207：整数划分方程

欧拉计划

Integer partition equations

For some positive integers k, there exists an integer partition of the form   4^t = 2^t + k,
where 4^t, 2^t, and k are all positive integers and t is a real number.

The first two such partitions are 4¹ = 2¹ + 2 and 4^1.5849625... = 2^1.5849625... + 6.

Partitions where t is also an integer are called perfect.
For any m ≥ 1 let P(m) be the proportion of such partitions that are perfect with k ≤ m.
Thus P(6) = 1/2.

In the following table are listed some values of P(m)

   P(5) = 1/1
   P(10) = 1/2
   P(15) = 2/3
   P(20) = 1/2
   P(25) = 1/2
   P(30) = 2/5
   ...
   P(180) = 1/4
   P(185) = 3/13

Find the smallest m for which P(m) < 1/12345.

题目：

对一些正整数 k 来说，存在一个整数划分，它具有 4^t = 2^t + k 的形式，其中，4^t， 2^t，k 都是正整数而 t 则是实数。

前两个这样的划分分别是 4¹ = 2¹ + 2 和 4^1.5849625... = 2^1.5849625... + 6。

如果这个划分中的 t 值 也是整数的话，称之为完美划分。

对于任意大于等于 1 的 m，定义 P(m) 为 k ≤ m 得到的分割中，完美分割所占比例，

因此，P(6) = 1/2。

下表是一些列举的 P(m) 的值：

        P(5) = 1/1
        P(10) = 1/2
        P(15) = 2/3
        P(20) = 1/2
        P(25) = 1/2
        P(30) = 2/5
        ...
        P(180) = 1/4
        P(185) = 3/13

请给出满足 P(m) < 1/12345 的最小的 m 值。

fc1735

1. #include<stdio.h>
   
2. #define NUM 12345
   
3. 
   
4. int main()
   
5. {
   
6.         long start ;
   
7.         long count=0;
   
8.         for(start=2;;start++){
   
9.                 long tmp=start;
   
10.                 while(!(tmp&1)&&tmp!=1){
    
11.                         tmp>>=1;
    
12.                 }
    
13.                 count+=tmp==1?1:0;
    
14.                 if(count*NUM<start-1)
    
15.                         break;
    
16.                
    
17.         }
    
18.         start<<=1;
    
19.         start--;
    
20.         start*=start;
    
21.         start--;
    
22.         start>>=2;
    
23.         printf("%ld",start);
    
24. }
    

复制代码