Detailed mathematical approach

Problem Summary

We must count positive integers \(n \le N\) whose number of divisors satisfies

$\tau(n)\equiv 1 \pmod{6}.$

The C++, Python, and Java implementations evaluate this count for \(N=10^{36}\). A direct scan up to \(10^{36}\) is impossible, so the solution rewrites the divisor condition into a rigid factorization pattern and then counts those patterns efficiently.

Mathematical Approach

Write the prime factorization of \(n\) as

$n=\prod_i p_i^{e_i}.$

Then the divisor-count function is

$\tau(n)=\prod_i (e_i+1).$

The problem is therefore to characterize exactly when this product is congruent to \(1\) modulo \(6\).

Step 1: Translate \(\tau(n)\equiv 1 \pmod{6}\) into congruences on the exponents

If a product is congruent to \(1\) modulo \(6\), then it is odd and also not divisible by \(3\). Hence every factor \(e_i+1\) must itself be odd and must avoid divisibility by \(3\). The only possible residue classes are

$e_i+1\equiv 1 \text{ or } 5 \pmod{6}.$

Equivalently, every exponent must satisfy

$e_i\equiv 0 \text{ or } 4 \pmod{6}.$

So an integer contributes exactly when each prime exponent is of the form \(6k\) or \(6k+4\). No other residue class can appear.

Step 2: Rewrite every admissible integer as \(a^6 b^4\)

For each prime exponent write

$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$

Now define

$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$

Then

$n=a^6 b^4.$

The integer \(b\) is squarefree because each prime enters it at most once. There is no need to impose \(\gcd(a,b)=1\): a prime may appear in both factors, and the exponent formula still stays unique because \(\beta_i\) records whether the residue class is \(0\) or \(4\) modulo \(6\).

Conversely, any number of the form \(a^6 b^4\) with squarefree \(b\) has prime exponents \(6k\) or \(6k+4\), so this description is exact.

Step 3: Reduce the congruence to a parity condition on \(b\)

If a prime contributes only through \(a^6\), then its divisor factor is

$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$

If that prime also appears in \(b\), then the exponent becomes \(6\alpha_i+4\), so

$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$

Therefore

$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$

where \(\omega(b)\) denotes the number of distinct prime factors of \(b\). Hence

$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ is even}.$

The original problem is now equivalent to counting pairs \((a,b)\) such that

$a^6 b^4\le N,$

\(b\) is squarefree, and \(b\) has an even number of distinct prime factors.

Step 4: Separate the outer variable \(a\) from the inner count over \(b\)

Fix \(a\). Then \(b\) must satisfy

$b\le \left(\frac{N}{a^6}\right)^{1/4}.$

Define

$E(x)=\#\{b\le x:\ b\text{ squarefree and }\omega(b)\text{ even}\}.$

Then the desired count becomes

$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$

This is exactly the outer summation implemented by the program.

Step 5: Express \(E(x)\) through squarefree counting and the Mertens function

Let

$Q(x)=\#\{n\le x:\ n\text{ is squarefree}\}.$

The classical Möbius inversion identity for the squarefree indicator is

$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d),$

so summing over \(n\le x\) gives

$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$

Now split the squarefree numbers into two classes: \(E(x)\) for even \(\omega\), and \(O(x)\) for odd \(\omega\). Then

$Q(x)=E(x)+O(x).$

On squarefree integers we have

$\mu(n)=(-1)^{\omega(n)},$

hence the Mertens function

$M(x)=\sum_{n\le x}\mu(n)$

satisfies

$M(x)=E(x)-O(x).$

Solving the two linear equations gives the key formula

$E(x)=\frac{Q(x)+M(x)}{2}.$

So the problem reduces to repeated evaluations of a squarefree summatory function and a Mertens summatory function.

Worked Example: \(N=100\)

Here

$\left\lfloor 100^{1/6}\right\rfloor=2,$

so only \(a=1\) and \(a=2\) are possible.

For \(a=1\), we have

$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$

The squarefree integers up to \(3\) are \(1,2,3\). Their values of \(\omega\) are \(0,1,1\), so only \(1\) has even parity. This contributes \(1\).

For \(a=2\), we have

$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$

so again the contribution is \(1\).

Therefore

$F(100)=1+1=2.$

The two valid integers are \(1\) and \(64=2^6\). By contrast, \(16=2^4\) is excluded because then \(\omega(b)=1\), so \(\tau(16)=5\not\equiv 1 \pmod{6}\).

How the Code Works

The implementation first precomputes Möbius values up to a fixed cutoff using a sieve, and from that it builds prefix sums for both \(\mu(n)\) and the squarefree indicator. Those prefix tables immediately answer small queries for \(Q(x)\) and \(M(x)\).

For larger arguments, the Mertens function is evaluated with the standard quotient-grouped recursion: values of \(\left\lfloor n/k\right\rfloor\) repeat over long intervals, so the recursion processes equal-quotient blocks together and stores the results in a memo table. The squarefree count \(Q(x)\) is obtained directly from the Möbius summation formula above.

Finally, the C++, Python, and Java implementations iterate over all \(a\le \lfloor N^{1/6}\rfloor\), compute the exact fourth-root bound for \(b\), evaluate \(E(x)=(Q(x)+M(x))/2\), and add that contribution to the answer. The integer-root calculations are corrected after the floating-point estimate, and the large-integer variants use wider arithmetic so that boundary cases near perfect powers are handled exactly.

Complexity Analysis

Let

$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$

The outer summation has \(A\) iterations. The sieve-style preprocessing up to the fixed cutoff costs linear or near-linear time in that cutoff and the same order of memory. Each squarefree query uses the sum

$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$

so its direct part is \(O(\sqrt{x})\), with \(x\le X\). The Mertens queries benefit from memoization over quotient blocks, so repeated large values are reused instead of recomputed. For the target problem, \(X=10^9\), hence \(\sqrt{X}\approx 31623\), which makes this strategy entirely practical. It is vastly faster than enumerating or factoring every \(n\le N\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=641
2. Divisor function: Wikipedia — Divisor function
3. Square-free integer: Wikipedia — Square-free integer
4. Möbius function: Wikipedia — Möbius function
5. Mertens function: Wikipedia — Mertens function
6. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle