Solution

Answer: 44043947822

Let

$$4^t = 2^t + k.$$

We are asked about positive integers $k$ for which such a partition exists, and among them, those where $t\in\mathbb Z$ (“perfect” partitions).

We want the smallest $m$ such that

$$P(m) < \frac1{12345},$$

where $P(m)$ is the proportion of partitions with $k\le m$ that are perfect.

Step 1: Rewrite the equation

Set

$$x = 2^t.$$

Then

$$4^t = (2^t)^2 = x^2,$$

so the defining equation becomes

$$x^2 = x + k.$$

Hence

$$k = x^2 - x = x(x-1).$$

Since $k$ must be an integer, $x$ must be an integer as well (because $x$ satisfies the monic polynomial $x^2-x-k=0$; an integer root condition gives $x\in\mathbb Z$).

Thus every partition corresponds exactly to an integer

$$x=n\ge2,$$

with

$$k=n(n-1).$$

So the admissible $k$'s are precisely

$$2,6,12,20,30,\dots$$

matching the examples.

Step 2: Characterize perfect partitions

A partition is perfect when $t$ is an integer.

But $x=2^t$. Therefore:

$t\in\mathbb Z$
iff $x$ is a power of two.

So perfect partitions correspond to

$$x=2^a \quad (a\ge1),$$

giving

$$k = 2^a(2^a-1).$$

Step 3: Count partitions up to $m$

All partitions are indexed by integers $n\ge2$ with

$$k=n(n-1)\le m.$$

Suppose the largest such $n$ is $N$. Then

$$N(N-1)\le m < (N+1)N.$$

Hence the total number of partitions up to $m$ is

$$N-1$$

(since $n=2,3,\dots,N$).

Now count perfect partitions.

Perfect partitions occur when $n$ is a power of two:

$$n=2,4,8,\dots,2^A\le N.$$

So the number of perfect partitions is

$$A,$$

where

$$A=\lfloor \log_2 N\rfloor.$$

Therefore

$$P(m)=\frac{\lfloor \log_2 N\rfloor}{N-1}.$$

Step 4: Solve the inequality

We need

$$\frac{\lfloor \log_2 N\rfloor}{N-1}<\frac1{12345}.$$

Let

$$a=\lfloor \log_2 N\rfloor.$$

Then

$$2^a \le N < 2^{a+1}.$$

The inequality becomes

$$12345a < N-1,$$

$$N > 12345a+1.$$

To minimize $m$, we minimize $N$. So for each $a$, the smallest candidate is

$$N = 12345a+2.$$

But this $N$ must satisfy

$$\lfloor \log_2 N\rfloor = a,$$

i.e.

$$2^a \le 12345a+2 < 2^{a+1}.$$

We test values of $a$.

$a=16$:

$$12345\cdot16+2=197522,$$

but

$$2^{16}=65536,\qquad 2^{17}=131072.$$

Too large.

$a=17$:

$$12345\cdot17+2=209867,$$

and

$$2^{17}=131072,\qquad 2^{18}=262144.$$

This works.

Thus the minimal valid $N$ is

$$N=209867.$$

Then the smallest corresponding $m$ is the smallest value with exactly this $N$, namely

$$m=N(N-1).$$

$$m=209867\cdot209866.$$

Compute:

$$209867^2 = 44,044,151,689,$$

hence

$$m=209867^2-209867 =44,044,151,689-209,867 =44,043,941,822.$$

Python implementation

import math

TARGET = 12345

a = 1

while True:
    # smallest N satisfying:
    # a / (N - 1) < 1 / TARGET
    N = TARGET * a + 2

    # check whether floor(log2(N)) == a
    if (1 << a) <= N < (1 << (a + 1)):
        m = N * (N - 1)
        print(m)
        break

    a += 1

Code walkthrough

TARGET = 12345

We need $P(m) < 1/12345$.

a = 1

Here $a=\lfloor \log_2 N\rfloor$, which equals the number of perfect partitions.

N = TARGET * a + 2

From

$$\frac{a}{N-1}<\frac1{12345},$$

we derive

$$N > 12345a+1.$$

The smallest integer satisfying this is

$$N=12345a+2.$$

if (1 << a) <= N < (1 << (a + 1)):

This checks

$$2^a \le N < 2^{a+1},$$

which ensures

$$\lfloor\log_2 N\rfloor=a.$$

m = N * (N - 1)

The smallest $m$ corresponding to this $N$ is

$$m=N(N-1).$$

Small-example verification

Take $m=30$.

The valid partitions are:

$$2,6,12,20,30$$

corresponding to $n=2,3,4,5,6$.

Perfect ones occur at $n=2,4$, i.e. $k=2,12$.

$$P(30)=\frac25,$$

matching the statement.

Also:

$m=180$ corresponds to $N=14$,
perfect $n$'s are $2,4,8$,
so $P(180)=3/12=1/4$,

again matching the problem.

Final verification

We found:

$$N=209867,$$

giving

$$P(m)=\frac{17}{209866}.$$

Indeed,

$$17\cdot12345=209865<209866,$$

$$\frac{17}{209866}<\frac1{12345}.$$

For the previous $N=209866$,

$$\frac{17}{209865}=\frac1{12345},$$

so our value is exactly the first one below the threshold.

Thus the result is consistent and minimal.

Answer: 44043941822

Project Euler Problem 207