Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/build_graph.py

Last active October 26, 2026 21:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Hermann-SW/12c7644ac0c75b4eb019f76c3f023fe5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Hermann-SW/12c7644ac0c75b4eb019f76c3f023fe5 to your computer and use it in GitHub Desktop.
Download ZIP
Latex labels for Graphviz (work in progress)
Raw
build_graph.py
This Python script became obsolete with this new repo:
https://github.com/Hermann-SW/graphviz_latex_pipeline
Because that repo's texdot.py compiles the LaTeX in each node or edge separately, with the real LaTeX.
You can still access this gist's Python code by opening the file at earlier revisions.
@Hermann-SW

Hermann-SW commented Sep 3, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

Work in progress, but does some nice stuff already.
(many many iterations working with gemini.google.com)

Below is the rendered graph_output.pdf, with Latex cases environment already working!

...
theo_3_47_label = latex_to_graphviz_html(
        r"""\textbf{Theo 3.47 }For cyclic group G:\\ G \cong \begin{cases}
            \mathbb{Z} & \text{for }G\text{ infinite,}\\
            \Z /|G|\mathbb{Z} & \text{for }G\text{ finite.} \end{cases}"""
)
...
image

@Hermann-SW

Hermann-SW commented Sep 3, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

Execute:

$ python build_graph.py 
Generated .dot file:

digraph G {
    layout=neato;
    overlap=prism;
    sep="+15";
    node [shape=box, fontsize=12, margin="0.15,0.1"];

    rankdir=LR

    Def_2_1 [label=<<B>Def 2.1 </B>a: ℕ →ℂ is &quot;number-theoretic function&quot; >];
    Ex_2_2a [label=<<B>Ex 2.2a </B>for s∈ℂ: ι<SUP>s</SUP>(n) := n<SUP>s</SUP> ∀n ∈ℕ is s-th power<BR/>function (s=0 constant one function, identity ι<SUP>1</SUP> =: ι)>];
    prop_3_38 [label=<<B>Prop 3.38 </B>G finite abelian group:<BR/>        G is cyclic ⇔∃g∈G with ord(g)=|G|>];
    prop_3_39 [label=<<B>Prop 3.39 </B>G finite abelian group,<BR/>g∈G, m∈ℤ: ord(g)|m ⇔g<SUP>m</SUP>=1>];
    theo_3_47 [label=<<TABLE BORDER="0" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0"><TR><TD BORDER="0" ALIGN="LEFT" COLSPAN="2"><B>Theo 3.47 </B>For cyclic group G:</TD></TR><TR><TD BORDER="0" VALIGN="MIDDLE" ALIGN="LEFT"> G  ≅ </TD><TD BORDER="0" VALIGN="MIDDLE" ALIGN="LEFT"><TABLE BORDER="0" CELLBORDER="0" CELLSPACING="0" CELLPADDING="1"><TR><TD ROWSPAN="2" VALIGN="MIDDLE" ALIGN="RIGHT" BORDER="0"><FONT POINT-SIZE="22">&#123;</FONT></TD><TD ALIGN="LEFT" VALIGN="MIDDLE" BORDER="0">ℤ</TD><TD ALIGN="LEFT" VALIGN="MIDDLE" BORDER="0">&nbsp;&nbsp;&nbsp;&nbsp;for G infinite,</TD></TR><TR><TD ALIGN="LEFT" VALIGN="MIDDLE" BORDER="0">ℤ/|G|ℤ</TD><TD ALIGN="LEFT" VALIGN="MIDDLE" BORDER="0">&nbsp;&nbsp;&nbsp;&nbsp;for G finite.</TD></TR></TABLE></TD><TD BORDER="0" VALIGN="MIDDLE" ALIGN="LEFT"></TD></TR></TABLE>>];
    { prop_3_38 prop_3_39 } -> theo_3_47;
}
$

graph_output.pdf file gets created from created .dot file automatically:

$ ls -lst | head -2
total 13891660
     24 -rw-rw-r-- 1 hermann hermann      24281 Sep  3 17:24 graph_output.pdf
$

@Hermann-SW

Hermann-SW commented Sep 3, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

build_graph.py transpiles Latex "...^..." and "..._..." to "<SUP>...</SUP>" and "<SUB>...</SUB>" which works nicely in Graphviz HTML labels as seen above. Unfortunately SUP/SUB are not supported by viz-js from Mike Daines, so I created new issue:
mdaines/viz-js#409

GraphvizFiddle share link
image

@Hermann-SW

Hermann-SW commented Sep 3, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

Nice short script eg. allowing generation of new output in vi editor [my preferred editor since 1990 ;-)] while editing build_graph.py:

  • press :, then w and <ENTER> to write changes
  • press :, then !, P and <ENTER> to run the script and update PDF viewer displaying graph_output.pdf
$ cat /usr/local/bin/P
#!/bin/bash
python build_graph.py
$

build_graph.py does abort in case of an unknown macro and reports the macro name as well as the line number with the unknown macro (here when executed from within vi as described before):

Traceback (most recent call last):
  File "/home/hermann/Downloads/build_graph.py", line 248, in <module>
    def_label = latex_to_graphviz_html(
                ^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/hermann/Downloads/build_graph.py", line 194, in latex_to_graphviz_html
    raise ValueError(f"Unknown macro \\{missing_node.macroname}")
ValueError: Unknown macro \mathBb

shell returned 1

Press ENTER or type command to continue

@Hermann-SW

Hermann-SW commented Sep 3, 2026

Copy link
Copy Markdown
Author

Latest gist output …
image

@Hermann-SW

Hermann-SW commented Sep 5, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

Added sections 3.3 “prime residue classes and Fermat-Euler theorem” and 3.4 “cyclic groups” of (German language) lecture script sitting behind Heidelberg University VPN. From definition 3.13 until theorem 3.49. More:
https://forum.graphviz.org/t/latex-labels-for-graphviz-work-in-progress/3402/3

Latest 10% screenshot below, full PDF for browser view:
https://stamm-wilbrandt.de/prime_residue_classess_and_Fermat-Euler_theorem.cyclic_groups.pdf
image

@Hermann-SW

Hermann-SW commented Sep 11, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

https://forum.graphviz.org/t/latex-labels-for-graphviz-work-in-progress/3402
https://forums.raspberrypi.com/viewtopic.php?t=400510
https://www.mersenneforum.org/node/1125625

@Hermann-SW

Hermann-SW commented Oct 14, 2026

Copy link
Copy Markdown
Author

https://latex.org/forum/viewtopic.php?t=36377

@Hermann-SW

Hermann-SW commented Oct 26, 2026

Copy link
Copy Markdown
Author

Unrelated, just for sharing AI markdown output:

While $n$ itself is the information-theoretic minimum at 64 bits, recovering its prime factors from $n$ requires integer factorization. However, because every integer $n \in (1, 2^{64})$ maps bijectively to a unique prime multiset, we can rearrange the bits of $n$'s prime factors so that the factorization can be unpacked in $O(1)$ time using only hardware bit-manipulation instructions (TZCNT, LZCNT, shifts, and masks) without factoring.

Depending on whether you want zero lookup tables or maximum bit density, the optimal packing takes 126 bits (zero tables), 80 bits / 10 bytes (a small L3-cache lookup table), or 72 bits / 9 bytes (entropy-shared header + wheel reduction).

1. Fundamental Structural Invariants for $1 &lt; n &lt; 2^{64}$

Before packing, we exploit four tight number-theoretic invariants that hold for every $n \in [2, 2^{64}-1]$:

  1. Bounded Factor Counts:

    • Distinct primes ($k$): At most $k \le 15$, since the 16th primorial $2 \cdot 3 \cdot 5 \cdots 53 \approx 3.26 \times 10^{19}$ exceeds $2^{64}$. At most 14 distinct odd primes can divide $n$.

    • Total multiplicity ($\Omega = \sum_{i=1}^k e_i$): At most $63$ (for $2^{63}$), and at most $39$ odd prime factors counted with multiplicity (since $3^{40}$ exceeds $2^{64}$).

  2. Factoring Out $2^{e_2}$: Write $n = 2^{e_2} \cdot q_1 q_2 \cdots q_r$, where $e_2 \ge 0$ is the exponent of $2$, and $3 \le q_1 \le q_2 \le \dots \le q_r$ are the odd prime factors listed with multiplicity (sorted by non-decreasing bit-length). Once $q_1, \dots, q_r$ are unpacked in sorted order, grouping equal adjacent primes into $(p_i, e_i)$ takes a single pass of at most 39 comparisons ($O(1)$).

  3. The Log-Sum Invariant ($\le 63$): For each odd prime $q_j \ge 3$, let $s_j = \lfloor \log_2 q_j \rfloor \ge 1$ be the bit index of its most significant bit. Because every odd prime satisfies $q_j \ge 2^{s_j} + 1$, we have:

    $$2^{e_2 + \sum_{j=1}^r s_j} \le 2^{e_2} \prod_{j=1}^r q_j = n \le 2^{64} - 1 \implies e_2 + \sum_{j=1}^r s_j \le 63$$
  4. The "Free MSB & LSB" Property of Odd Primes: Every odd prime $q_j \ge 3$ has its most significant bit fixed to 1 (at bit $s_j$) and its least significant bit fixed to 1 (since it is odd):

    $$q_j = 2^{s_j} + 2 u_j + 1, \quad u_j \in \left[0, 2^{s_j - 1} - 1\right]$$
    Thus, given $s_j$, $q_j$ is uniquely determined by only $s_j - 1$ interior bits $u_j$. (Notably, $q_j = 3$ has $s_j = 1$ and requires 0 interior bits.) Summing over all odd prime factors:

    $$\text{Total interior bits } m = \sum_{j=1}^r (s_j - 1) = \left(\sum_{j=1}^r s_j\right) - r \le 63 - e_2 - r \le 62\text{ bits}$$

2. The Core Trick: Overlapping Primes in a Single 64-Bit Word W

Because every odd prime $q_j$ both starts with a 1-bit (LSB) and ends with a 1-bit (MSB), we can chain $q_1, q_2, \dots, q_r$ end-to-end inside a single 64-bit word W (uint64_t) by overlapping the MSB 1-bit of $q_j$ with the LSB 1-bit of $q_{j+1}$!

Define the cumulative fencepost bit positions:

$$P_0 = e_2, \quad P_1 = e_2 + s_1, \quad P_2 = e_2 + s_1 + s_2, \quad \dots, \quad P_r = e_2 + \sum_{j=1}^r s_j \le 63$$
We construct the 64-bit data word W by bitwise-ORing each odd prime shifted to its fencepost start:

$$\texttt{W} = 2^{P_0} \ \Big\vert{} \ \bigoplus_{j=1}^r \left(q_j \ll P_{j-1}\right)$$
Look at what this single 64-bit integer W gives you immediately in hardware:

  • Bits $0 \dots P_0 - 1$ are 0, and bit $P_0$ is 1: Therefore, the exponent of $2$ is extracted in 1 CPU cycle via e2 = P_0 = tzcnt(W) (count trailing zeros).

  • Bit $P_r$ is the highest set 1-bit of W: Therefore, $P_r = 63 - \text{lzcnt}(W)$ is also extracted in 1 CPU cycle! (If W has only one set bit, i.e. (W & (W - 1)) == 0, then $r = 0$ and $n = 2^{e_2}$.)

  • Every prime $q_j$ is sitting verbatim in W between bits $P_{j-1}$ and $P_j$: Once you know the fencepost positions $P_0, P_1, \dots, P_r$, extracting $q_j$ is a single shift and mask:

    $$q_j = (\texttt{W} \gg P_{j-1}) \ \&amp; \ \left((2 \ll (P_j - P_{j-1})) - 1\right)$$
Thus, W (64 bits) already holds $e_2$, $P_r$, and all interior bits of every prime factor. The only remaining information required to unpack the factorization is identifying which internal bit positions $P_1, \dots, P_{r-1}$ are the boundaries between primes.

3. Three Optimal $O(1)$ Packing Schemes

Depending on your memory-versus-table budget, here are the three best ways to encode the fencepost boundaries $P_1, \dots, P_{r-1}$ alongside W:

Scheme | Bits per Number | Shared Lookup Table | O(1) Unpack Cost | Best Use Case -- | -- | -- | -- | -- A. Raw Fencepost Pair (W, F) | 126 bits (16 B aligned) | 0 bytes | ~15 CPU cycles (pure ALU/BMI2) | Zero cache pressure, SIMD-friendly B. W + Partition Shape ID | 80 bits (10 bytes) | ~2.4 MB | 1 table lookup + ~15 ALU cycles | Best balance of high density & simplicity C. Slack-Shared + Wheel-30 | 72 bits (9 bytes) | ~4.5 MB | 2 table lookups + ~25 ALU cycles | Maximum practical $O(1)$ bit density

Scheme A: Zero-Table 126-Bit Packing (W + Fencepost Mask F)

If you want zero lookup tables and blazing-fast register-only unpacking, store two 64-bit words (W, F):

  1. W (uint64_t, 64 bits): The overlapped prime word defined above.

  2. F (uint64_t, 62 bits): A bitmask with 1s at the internal fenceposts $P_1, P_2, \dots, P_{r-1}$ (since $P_0$ and $P_r$ are already the lowest and highest set bits of W, bits $0$ and $63$ of F are never needed, using at most 62 bits).

C
#include <stdint.h>

typedef struct {

uint64_t p;

uint8_t  e;

} PrimePower;


// Unpacks n's prime factorization in O(1) time with ZERO lookup tables

int unpack_factorization_126(uint64_t W, uint64_t F, PrimePower out[15]) {

int k = 0;

int p0 = __builtin_ctzll(W); // Exponent of 2 (P_0)

if (p0 > 0) {

out[k++] = (PrimePower){2, (uint8_t)p0};

}

// Clear lowest fencepost bit P_0; remaining bits in F | (1ULL << P_r) mark odd primes

uint64_t fences = F;

int prev = p0;

uint64_t last_prime = 0;


<span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">while</span> (fences != <span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">0</span>) {
    <span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">int</span> next = __builtin_ctzll(fences);
    fences &amp;= fences - <span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">1</span>; <span class="hljs-comment" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">// Clear lowest set fencepost</span>
    <span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">int</span> s = next - prev;
    <span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">uint64_t</span> q = (W &gt;&gt; prev) &amp; ((<span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">2ULL</span> &lt;&lt; s) - <span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">1ULL</span>);
    <span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">if</span> (q == last_prime) {
        out[k - <span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">1</span>].e++;
    } <span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">else</span> {
        out[k++] = (PrimePower){q, <span class="hljs-number" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">1</span>};
        last_prime = q;
    }
    prev = next;
}
<span class="hljs-keyword" style="font-family: Google Sans Text, sans-serif !important; line-height: 1.15 !important; margin-top: 0px !important; margin-left: 0px !important; margin-right: 0px !important;">return</span> k;



}

Scheme B: The 80-Bit (10-Byte) "Partition Index" Packing

Notice why storing F as a raw 64-bit bitmask in Scheme A wastes space:

  1. From W alone, we already know both $P_0 = \text{tzcnt}(W)$ and $P_r = 63 - \text{lzcnt}(W)$, so we already know the exact sum of the step sizes:

    $$S = \sum_{j=1}^r s_j = P_r - P_0 \in [0, 63]$$
  2. Because multiplication is commutative, we sort the odd prime factors so that their step sizes are non-decreasing:

    $$1 \le s_1 \le s_2 \le \dots \le s_r, \quad \sum_{j=1}^r s_j = S$$
    Therefore, $(s_1, s_2, \dots, s_r)$ is simply an integer partition of $S$!

  3. How many partitions of $S$ can actually correspond to valid primes with $\prod_{j=1}^r q_j &lt; 2^{64 - e_2}$?
    Every prime with     $\lfloor \log_2 q_j \rfloor = s_j$ is at least $p_{\min}(s_j) = \text{next_prime}(2^{s_j})$, which carries a mandatory fractional bit-excess $\delta_{\min}(s_j) = \log_2(p_{\min}(s_j)) - s_j$:

    • $s = 1 \ (q \ge 3) \implies \delta_{\min}(1) = \log_2(3) - 1 \approx 0.585\text{ bits}$

    • $s = 2 \ (q \ge 5) \implies \delta_{\min}(2) = \log_2(5) - 2 \approx 0.322\text{ bits}$

    • $s = 3 \ (q \ge 11) \implies \delta_{\min}(3) = \log_2(11) - 3 \approx 0.459\text{ bits}$

    For a partition of $S$ to be realizable by a product under $2^{64}$, the sum of these excesses must satisfy $\sum_{j=1}^r \delta_{\min}(s_j) &lt; 64 - S - e_2$.

    • When $S$ is near $63$, $64 - S$ is tiny, which eliminates almost all partitions containing small parts ($1, 2, 3$).

    • When $S$ is small, the unconstrained partition number $p(S)$ is already small.
      Consequently,       for every $S \in [1, 63]$, the number of realizable partitions of $S$ is strictly less than $2^{16} = 65,536$!

Packing format (80 bits = 10 bytes):

  • Bytes 0–7 (uint64_t W): The 64-bit overlapped prime word.

  • Bytes 8–9 (uint16_t shape_idx): The 16-bit index of the partition $(s_1, \dots, s_r)$ within the precomputed table PARTITION_FENCES[S][shape_idx], which directly returns the 64-bit relative fencepost mask F_rel in a single memory lookup!

  • Decoding: Compute e2 = tzcnt(W), S = (63 - lzcnt(W)) - e2, fetch F = PARTITION_FENCES[S][shape_idx] << e2, and run the exact same loop as Scheme A.

Scheme C: Pushing to 72 Bits (9 Bytes) via Slack Sharing & Wheel-30

To shave off another byte (down to 72 bits / 9 bytes):

  1. Exploit the $63 - S + r$ Slack inside W:
    When a number has many prime factors (    $r$ is large, so the number of possible partitions is larger), the actual number of interior bits $m = \sum_{j=1}^r (s_j - 1) = S - r$ shrinks by $r$. Conversely, when $m$ is near $62$ ($r = 1$ or $2$), there are fewer than $35$ possible partitions. By packing the $m$ interior bits in the low bits of a 72-bit integer and storing a combined (e2, partition_id) state in the upper $72 - m$ bits, every valid (shape, interior_bits) combination across $1 &lt; n &lt; 2^{64}$ maps into fewer than $2^{72}$ states.

  2. Wheel-30 Compression ($W_{30}$):
    Every prime     $q \ge 7$ lies in one of $\phi(30) = 8 = 2^3$ residue classes modulo 30: ${1, 7, 11, 13, 17, 19, 23, 29}$. Writing $q = 30 m_q + \text{WHEEL30}[c]$ (where $c \in {0..7}$) and encoding $(m_q \ll 3) \mid c$ shrinks each prime $q \ge 7$ by a factor of $30/8 = 3.75$, saving an extra $\log_2(3.75) - 1 \approx 0.907$ bits per prime factor beyond LSB stripping and decoding in two instructions: (q_idx >> 3) * 30 + WHEEL30[q_idx & 7].

Bonus Case: If $n$ Itself Is Already Stored (64-Bit Key + 32-Bit Hint)

If your application already stores $n$ (e.g., in a hash table or sorted array of 64-bit keys) and you only want to attach an auxiliary hint for $O(1)$ factorization:

  • Never store the largest prime factor $q_r$ in the hint.

  • Store only $q_1, \dots, q_{r-1}$ (which all satisfy $q_j &lt; 2^{32}$ and $\prod_{j=1}^{r-1} q_j \le n / q_r$), and recover the final prime factor via a single 64-bit division:

    $$q_r = \frac{n}{2^{e_2} \prod_{j=1}^{r-1} q_j}$$

Interactive Bit-Packing Inspector

Use the interactive visualizer below to inspect how any 64-bit factorization is stripped of its fixed MSB/LSB bits, chained into the 64-bit word W, and paired with its fencepost mask F and 16-bit partition index:

Key takeaway: Because the MSB and LSB of every odd prime are both 1, chaining the primes inside W with overlapped endpoints means a single 64-bit word already stores $e_2$, the total bit-span $S$, and all interior bits of every prime factor—reducing the remaining metadata to a 16-bit partition index (80 bits total) or a 62-bit fencepost mask (126 bits with zero tables).

@Hermann-SW

Hermann-SW commented Oct 26, 2026

Copy link
Copy Markdown
Author

Short answer:
The only representation that guarantees O(1) retrieval of the full factorisation for every 64‑bit integer is to store the integer itself (i.e., the 64‑bit value of n). Any “compact” encoding that tries to keep the factorisation in fewer bits must either

  • allocate space for the worst‑case factorisation (which ends up using at least as many bits as the original 64‑bit number), or
  • give up the O(1) guarantee and factor the number on‑the‑fly.

Below is a more detailed explanation of why this is the case and what the theoretical limits are.

1. What does “O(1) access” mean here?

O(1) means that, given a pointer/identifier for a stored factorisation, you can retrieve the complete list of primes, exponents, and their count in a constant number of steps – independent of the size of n or the number of prime factors k.

To achieve that, the representation must provide random‑access to each component (the count k, each prime pᵢ, each exponent eᵢ) without any computation that depends on n.

The only way to have true random‑access to an arbitrary‑length list inside a fixed‑size memory layout is to reserve space for the maximum possible length and keep the data contiguous (or in a small fixed‑size array).

If the layout is variable‑length (e.g., a linked list, a dynamically‑sized array, or a compressed stream), you need to follow pointers or decode a variable‑length format – both of which are O(k) (or worse) where k is the number of prime factors.

2. How many prime factors can a 64‑bit number have?

The product of the first m distinct primes (the primorial #pₘ) grows roughly like e^{pₘ}.
We need the largest m such that the primorial is still < 2⁶⁴ ≈ 1.84 × 10¹⁹.

 m   Primes (first m)   Primorial   ≈ log₂ 
 1   2   2   1 
 2   2·3   6   ≈ 2.6 
 3   2·3·5   30   ≈ 4.9 
 4   2·3·5·7   210   ≈ 7.7 
 5   2·3·5·7·11   2310   ≈ 11.2 
 6   2·3·5·7·11·13   30030   ≈ 14.9 
 7   2·3·5·7·11·13·17   510510   ≈ 19 
 8   …·19   9699690   ≈ 23.2 
 9   …·23   223092870   ≈ 27.7 
 10   …·29   6469693230   ≈ 32.6 
 11   …·31   200560490130   ≈ 37.5 
 12   …·37   7420738134810   ≈ 42.8 
 13   …·41   304250263527210   ≈ 48.1 
 14   …·43   13082761331670030   ≈ 53.6 
 15   …·47   614889782588491410   ≈ 59.2 
 16   …·53   32589158477190044730   ≈ 64.9 > 2⁶⁴ 

Thus the maximum number of distinct prime factors for any integer < 2⁶⁴ is 15 (the primorial of the first 15 primes is still below 2⁶⁴; adding the 16‑th prime pushes it over).

In the absolute worst case for a prime number, k = 1 and the single prime can be as large as 2⁶⁴ − 1, requiring the full 64 bits just to store that prime.

3. Lower bound on any O(1) representation

Because a prime close to 2⁶⁴ must be representable, any format that allows O(1) retrieval of the factorisation must be able to store a 64‑bit value.

Consequently:

  • Minimum worst‑case size = 64 bits (plus a few bits for metadata such as k).
  • Storing the original number n already meets this lower bound.

Therefore no representation can be denser than “store the 64‑bit integer itself.”

Any attempt to “pack” the primes and exponents more tightly would have to sacrifice either:

  • the ability to represent every possible 64‑bit prime (you would run out of bits), or
  • the O(1) random‑access property (you would need to decode a variable‑length structure).

4. What if you are willing to reserve space for the worst‑case factorisation?

If you insist on a fixed‑size structure that always holds the full factorisation (so you can retrieve it in O(1) without any computation), you must allocate room for the maximum possible values of each field:

Field Maximum needed bits Reasoning
 k   4 bits (values 0–15) at most 15 distinct primes
 Prime pᵢ  64 bits each a single prime can be a 64‑bit number
 Exponent eᵢ  6 bits each (0–63) 2⁶⁴ ⇒ max exponent for base 2 is 64, so 6 bits suffice

If you allocate 15 slots (the worst‑case k), the raw storage would be:

15 × (64 bits prime + 6 bits exponent) = 15 × 70 = 1050 bits
≈ 132 bytes

plus a few bits for k and possible padding → ≈ 136 bytes per number.

That is more than twice the size of simply storing the original 8‑byte integer.

Even if you compress the primes (e.g., by delta‑encoding relative to the previous prime) you would still need extra bits for the encoding scheme, and the worst‑case (a single 64‑bit prime) would still occupy essentially the same 64 bits.

Hence, a densest‑possible O(1) layout is still larger than the original 64‑bit value.

5. Practical recommendation

Goal Best approach
Minimal storage, O(1) lookup of the value (not the factorisation) Store the 64‑bit integer n directly. Factorization can be done on demand (trial division, Pollard‑Rho, etc.) – not O(1) but very fast for a single number.
Guaranteed O(1) retrieval of the full factorisation Keep a pre‑computed table that maps each 64‑bit n to its factorisation. The table entry must be at least 64 bits (to hold the prime) plus overhead, so the overall space consumption is essentially the same as storing the numbers themselves, often much larger due to indexing.
Space‑critical applications where occasional factorisation is acceptable Store only the 64‑bit n and factor lazily when needed. Use a cache for frequently‑used numbers if the same factorisation is required repeatedly.
If you truly need both extreme density and O(1) factorisation This is impossible under the given constraints; you must trade one of the two properties.

6. TL;DR

The densest possible representation that still lets you read the complete factorisation in constant time must be able to hold a 64‑bit prime, so it needs at least 64 bits per entry. The simplest way to meet that lower bound is to store the original 64‑bit integer itself. Any “compact” encoding that tries to store primes and exponents separately either wastes more space (when you reserve room for the worst case) or cannot guarantee O(1) access.

In short: store the number; factor it on demand—or accept a much larger fixed‑size record if you truly require O(1) factorisation for every entry.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment