Project Euler

Distances in a Bee's Honeycomb

On a hexagonal lattice, define the Eisenstein norm of a point z = a + bomega (where omega = e^(2pi i/3)) as N(z) = a^2 - ab + b^2. Let C(n) be the number of Eisenstein integers of norm exactly n. F...

Source sync Apr 19, 2026

Problem #0354

Level Level 22

Solved By 530

Languages C++, Python

Answer 58065134

Length 395 words

modular_arithmeticsearchlinear_algebra

Consider a honey bee’s honeycomb where each cell is a perfect regular hexagon with side length $1$.

One particular cell is occupied by the queen bee.

For a positive real number $L$, Let $B(L)$ count the cells with distance $L$ from the queen bee cell (all distances are measured from centre to centre); you may assume that the honeycomb is large enough to accommondate for any distance we wish to condsider.

For example, $B(\sqrt {3}) = 6$, $B(\sqrt {21} = 12)$ and $B(\num {111111111}) = 54$.

Find the number of $L \leq 5 \times 10^{11}$ such that $B(L) = 450$.

Problem 354: Distances in a Bee’s Honeycomb

Mathematical Foundation

Theorem 1 (Representation count for Eisenstein norm). The number of Eisenstein integers of norm $n$ is

C(n) = 6\sum_{d \mid n} \chi(d)

where $\chi$ is the non-principal Dirichlet character modulo 3, defined by $\chi(d) = 0$ if $3 \mid d$ , $\chi(d) = 1$ if $d \equiv 1 \pmod{3}$ , and $\chi(d) = -1$ if $d \equiv 2 \pmod{3}$ .

Proof. The Eisenstein integers $\mathbb{Z}[\omega]$ form a unique factorization domain. The norm $N(a + b\omega) = a^2 - ab + b^2$ is multiplicative. The number of elements of norm $n$ equals $6 \sum_{d \mid n} \chi(d)$ , where the factor 6 accounts for the 6 units in $\mathbb{Z}[\omega]$ , and the Dirichlet series identity

\sum_{n=1}^{\infty} \frac{r(n)}{n^s} = \frac{6}{1 - 3^{-s}} \cdot L(s, \chi) \cdot \zeta(s)

(with appropriate normalization) encodes the multiplicative structure. This is a classical result; see, e.g., Ireland and Rosen, A Classical Introduction to Modern Number Theory, Chapter 9. $\square$

Lemma 1 (Multiplicative formula). Write $n = 3^a \prod_{i} p_i^{a_i} \prod_{j} q_j^{b_j}$ where $p_i \equiv 1 \pmod{3}$ and $q_j \equiv 2 \pmod{3}$ . Then

\sum_{d \mid n} \chi(d) = \prod_{i}(a_i + 1) \cdot \prod_{j} \frac{1 + (-1)^{b_j}}{2} = \begin{cases} \prod_i (a_i + 1) & \text{if all } b_j \text{ are even}, \\ 0 & \text{otherwise}. \end{cases}

Proof. Since $\chi$ is completely multiplicative, $\sum_{d \mid n} \chi(d)$ is a multiplicative function of $n$ . We evaluate it on prime powers:

$\sum_{d \mid 3^a} \chi(d) = 1$ (only $d=1$ contributes, since $\chi(3) = 0$ ).
$\sum_{d \mid p^a} \chi(d) = 1 + \chi(p) + \chi(p)^2 + \cdots + \chi(p)^a$ . For $p \equiv 1 \pmod{3}$ : $\chi(p) = 1$ , so the sum is $a + 1$ . For $q \equiv 2 \pmod{3}$ : $\chi(q) = -1$ , so the sum is $1 - 1 + 1 - \cdots = \frac{1 + (-1)^b}{2}$ .

Multiplying over all prime-power factors gives the result. $\square$

Corollary. $C(n) = 450$ if and only if all exponents $b_j$ of primes $\equiv 2 \pmod{3}$ are even, and $\prod_i (a_i + 1) = 75$ .

Proof. $C(n) = 450$ requires $6 \cdot \prod_i(a_i + 1) = 450$ , i.e., $\prod_i(a_i+1) = 75$ , with the even-exponent condition from Lemma 1. $\square$

Lemma 2 (Factorizations of 75). The unordered factorizations of $75 = 3 \times 5^2$ into factors $\ge 2$ (each factor corresponding to $a_i + 1$ for a distinct prime $p_i \equiv 1 \pmod 3$ ) are:

Factorization	Exponent tuple $(a_i)$
$75$	$(74)$
$25 \times 3$	$(24, 2)$
$15 \times 5$	$(14, 4)$
$5 \times 5 \times 3$	$(4, 4, 2)$

Proof. Exhaustive enumeration of ordered factorizations of 75 into parts $\ge 2$ , then reducing to unordered (multiset) factorizations. $\square$

Editorial

C(n) = 6 * (d1(n) - d2(n)) where d1, d2 count divisors == 1, 2 mod 3. Need d1(n) - d2(n) = 75 with all primes == 2 mod 3 at even exponents. Product of (a_i + 1) for primes == 1 mod 3 must equal 75. Exponent patterns: (74), (24,2), (14,4), (4,4,2). We generate primes up to limit^(1/2) via sieve. We then classify primes as type-1 (≡1 mod 3) or type-2 (≡2 mod 3). Finally, iterate over each exponent tuple from Lemma 2.

Pseudocode

Generate primes up to limit^(1/2) via sieve
Classify primes as type-1 (≡1 mod 3) or type-2 (≡2 mod 3)
For each exponent tuple from Lemma 2
Backtracking enumeration
Assign primes ≡1 (mod 3) to the exponent slots (decreasing order)
For each assignment, compute base = product of p_i^{a_i}
Remaining budget = limit / base
Multiply by 3^a for any a >= 0 with 3^a <= remaining
Multiply by q_j^{2*c_j} for primes q_j ≡2 (mod 3) with q_j^2 <= remaining
Count all valid combinations via DFS

Complexity Analysis

Time: The enumeration is bounded by the number of valid $n \le 10^{12}$ , which is 58065. The backtracking prunes branches aggressively when the partial product exceeds $10^{12}$ . In practice, runtime is dominated by the enumeration and is sub-second.
Space: $O(\pi(\sqrt{L}))$ for storing primes up to $\sqrt{10^{12}} = 10^6$ , plus $O(k)$ stack depth for the backtracking, where $k$ is the number of prime factors.

Answer

\boxed{58065134}

C++ project_euler/problem_354/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 354: Distances in a Bee's Honeycomb
 *
 * Find count of n <= 10^12 with C(n) = 450 where C(n) = 6*(d1(n) - d2(n))
 * and d1, d2 count divisors congruent to 1, 2 mod 3 respectively.
 *
 * We need d1(n) - d2(n) = 75, with all primes == 2 mod 3 having even exponents.
 * Product of (a_i + 1) for primes == 1 mod 3 must equal 75.
 *
 * Factorizations of 75: {75}, {25,3}, {15,5}, {5,5,3}
 * Exponent patterns: (74), (24,2), (14,4), (4,4,2)
 *
 * We enumerate using backtracking over primes.
 */

typedef long long ll;
const ll LIMIT = 1000000000000LL; // 10^12

// Primes == 1 mod 3 (up to a reasonable bound)
vector<ll> primes1; // primes p with p == 1 mod 3
vector<ll> primes2; // primes p with p == 2 mod 3

void sieve_primes(ll bound) {
    vector<bool> is_prime(bound + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= bound; i++) {
        if (!is_prime[i]) continue;
        for (ll j = i * i; j <= bound; j += i)
            is_prime[j] = false;
        if (i == 3) continue; // skip 3 itself
        if (i % 3 == 1) primes1.push_back(i);
        else if (i % 3 == 2) primes2.push_back(i);
    }
}

ll answer = 0;

// Count numbers <= limit that are products of even powers of primes == 2 mod 3
// (i.e., squares of squarefree numbers composed of primes == 2 mod 3) times powers of 3
// Actually: products of 3^a * product(q_j^{2*b_j}) for any a >= 0, b_j >= 1 or 0
// We need to count n <= limit of the form 3^a * m^2 where m is composed only of primes == 2 mod 3
// Wait -- not exactly. We need n such that n = base * k where base is the product of primes == 1 mod 3
// part, and k = 3^a * product(q_j^{2*c_j}) for any a >= 0, c_j >= 0.
// k can be any number whose odd part (removing factor 3) is a perfect square of a 2-mod-3-smooth number.

// Count of k <= L where k = 3^a * s^2, s composed of primes == 2 mod 3, a >= 0
// = sum_{a=0}^{...} count of s^2 <= L/3^a where s is product of primes == 2 mod 3
// This is complex. Let's use a simpler recursive enumeration.

// Count square numbers (including 1) up to L composed only of primes == 2 mod 3, times any power of 3
void count_multipliers(ll limit, int idx2, ll current, ll& cnt) {
    // current = product so far of (primes2 squares and powers of 3)
    // Add all powers of 3 multiplied by current
    ll val = current;
    while (val <= limit) {
        cnt++;
        val *= 3;
    }

    // Try adding q^2 for primes2[idx2], primes2[idx2+1], ...
    for (int i = idx2; i < (int)primes2.size(); i++) {
        ll q = primes2[i];
        ll q2 = q * q;
        if (current > limit / q2) break; // overflow check
        ll next = current * q2;
        while (next <= limit) {
            count_multipliers(limit, i + 1, next, cnt);
            if (next > limit / q2) break;
            next *= q2;
        }
    }
}

// Enumerate products of primes == 1 mod 3 with given exponent pattern
// exps is sorted decreasingly
void enumerate(vector<int>& exps, int idx, int p1_idx, ll current) {
    if (idx == (int)exps.size()) {
        // current is the "base" from primes == 1 mod 3
        // Now count multipliers: numbers m such that current * m <= LIMIT
        // and m = 3^a * (square from primes == 2 mod 3)
        ll rem = LIMIT / current;
        ll cnt = 0;
        count_multipliers(rem, 0, 1, cnt);
        answer += cnt;
        return;
    }

    int e = exps[idx];
    // Choose a prime from primes1[p1_idx..]
    int start = p1_idx;
    // If same exponent as previous, start from same index+1 to avoid duplicates
    // (handled by requiring increasing prime indices for same exponents)

    for (int i = start; i < (int)primes1.size(); i++) {
        ll p = primes1[i];
        ll pe = 1;
        bool overflow = false;
        for (int j = 0; j < e; j++) {
            if (pe > LIMIT / p) { overflow = true; break; }
            pe *= p;
        }
        if (overflow || pe > LIMIT) break;
        if (current > LIMIT / pe) break;

        ll next = current * pe;
        // For next exponent, if same value, start from i+1
        int next_start = (idx + 1 < (int)exps.size() && exps[idx+1] == e) ? i + 1 : 0;
        enumerate(exps, idx + 1, next_start, next);
    }
}

int main() {
    // Sieve primes up to sqrt(10^12) ~ 10^6
    sieve_primes(1000000);

    // Exponent patterns for product = 75
    // 75 = 75, 25*3, 15*5, 5*5*3
    vector<vector<int>> patterns = {
        {74},
        {24, 2},
        {14, 4},
        {4, 4, 2}
    };

    for (auto& pat : patterns) {
        enumerate(pat, 0, 0, 1);
    }

    cout << answer << endl;

    return 0;
}

Python project_euler/problem_354/solution.py

"""
Problem 354: Distances in a Bee's Honeycomb

Find count of n <= 10^12 with C(n) = 450 on the hexagonal lattice.

C(n) = 6 * (d1(n) - d2(n)) where d1, d2 count divisors == 1, 2 mod 3.
Need d1(n) - d2(n) = 75 with all primes == 2 mod 3 at even exponents.
Product of (a_i + 1) for primes == 1 mod 3 must equal 75.

Exponent patterns: (74), (24,2), (14,4), (4,4,2)
"""

def solve():
    LIMIT = 10**12

    # Sieve primes up to 10^6
    sieve_bound = 1000001
    is_prime = [True] * sieve_bound
    is_prime[0] = is_prime[1] = False
    for i in range(2, sieve_bound):
        if is_prime[i]:
            for j in range(i*i, sieve_bound, i):
                is_prime[j] = False

    primes1 = [p for p in range(2, sieve_bound) if is_prime[p] and p % 3 == 1]
    primes2 = [p for p in range(2, sieve_bound) if is_prime[p] and p % 3 == 2]

    answer = 0

    def count_multipliers(limit, idx2, current):
        """Count numbers <= limit of form 3^a * product(q_j^(2*c_j))"""
        cnt = 0
        # Count all powers of 3 times current
        val = current
        while val <= limit:
            cnt += 1
            val *= 3

        # Add squares of primes == 2 mod 3
        for i in range(idx2, len(primes2)):
            q = primes2[i]
            q2 = q * q
            if current * q2 > limit:
                break
            nxt = current * q2
            while nxt <= limit:
                cnt += count_multipliers(limit, i + 1, nxt)
                if nxt > limit // q2:
                    break
                nxt *= q2

        return cnt

    def enumerate_patterns(exps, idx, p1_idx, current):
        nonlocal answer
        if idx == len(exps):
            rem = LIMIT // current
            answer += count_multipliers(rem, 0, 1)
            return

        e = exps[idx]
        for i in range(p1_idx, len(primes1)):
            p = primes1[i]
            pe = p ** e
            if pe > LIMIT:
                break
            if current * pe > LIMIT:
                break

            nxt_start = i + 1 if (idx + 1 < len(exps) and exps[idx + 1] == e) else 0
            enumerate_patterns(exps, idx + 1, nxt_start, current * pe)

    # Exponent patterns for 75 = 75, 25*3, 15*5, 5*5*3
    patterns = [
        [74],
        [24, 2],
        [14, 4],
        [4, 4, 2],
    ]

    for pat in patterns:
        enumerate_patterns(pat, 0, 0, 1)

    print(answer)

if __name__ == "__main__":
    solve()