Prime numbers and set distances

by: Eric S. Téllez

This demonstration represents integers by their prime factor sets and uses set-distance functions to find numerically similar numbers. It is a self-contained demo — no dataset download needed — that shows SearchGraph with sparse set data, UMAP visualization, and the allknn operation.

Note: set the JULIA_NUM_THREADS=auto environment variable (or pass -t auto to Julia) for best performance.

using SimilaritySearch, SimSearchManifoldLearning, Primes, Plots, StatsBase, LinearAlgebra, Markdown, Random

Dataset

Each integer is represented as the sorted vector of its distinct prime factors.

n = 100_000
F = Vector{Vector{Int32}}(undef, n + 1)

encode_factors(num) = sort!(Int32[convert(Int32, f) for f in factor(Set, num)])

F[1] = Int32[1]
for i in 2:n+1
    F[i] = encode_factors(i)
end

db   = VectorDatabase(F)
dist = Dist.Sets.Dice()           # other options:
# dist = Dist.Sets.Jaccard()
# dist = Dist.Sets.Intersection()
# dist = Dist.Sets.CosineSet()

Index construction

1G   = SearchGraph(dist, db)
ctx = SearchGraphContext(hyperparameters_callback=OptimizeParameters(MinRecall(0.95)))
2index!(G, ctx)
3optimize_index!(G, ctx, MinRecall(0.9))
1
Positional constructor SearchGraph(dist, db) with the set distance.
2
Indexes all 100 001 integers.
3
Optimizes beam-search hyperparameters for 90 % recall.

Searching

function search_and_render(index, ctx, qnum, qenc, res, k)
    res = reuse!(res, k)
    @time search(index, ctx, qenc, res)

    L = [
        """## Result list for num: $(qnum), factors: $qenc""",
        """| nn | num | factors | dist |""",
        """|----|-----|---------|------|"""
    ]
    for (j, p) in enumerate(IdDistView(res))
        push!(L, """| $j | $(p.id) | $(index[p.id]) | $(round(p.dist, digits=3)) |""")
    end

    Markdown.parse(join(L, "\n"))
end

res = knnqueue(ctx, 12)
for qnum in [42, 51, 1000, 1492, 3192]
    qenc = encode_factors(qnum)
    search_and_render(G, ctx, qnum, qenc, res, maxlength(res)) |> display
end
  0.000308 seconds (3 allocations: 64 bytes)
  0.000676 seconds (3 allocations: 64 bytes)
  0.000340 seconds (3 allocations: 64 bytes)
  0.000675 seconds (3 allocations: 64 bytes)
  0.000105 seconds (3 allocations: 64 bytes)

Result list for num: 42, factors: Int32[2, 3, 7]

nn num factors dist
1 42 Int32[2, 3, 7] 0.0
2 84 Int32[2, 3, 7] 0.0
3 126 Int32[2, 3, 7] 0.0
4 168 Int32[2, 3, 7] 0.0
5 252 Int32[2, 3, 7] 0.0
6 294 Int32[2, 3, 7] 0.0
7 336 Int32[2, 3, 7] 0.0
8 378 Int32[2, 3, 7] 0.0
9 504 Int32[2, 3, 7] 0.0
10 756 Int32[2, 3, 7] 0.0
11 588 Int32[2, 3, 7] 0.0
12 1008 Int32[2, 3, 7] 0.0

Result list for num: 51, factors: Int32[3, 17]

nn num factors dist
1 51 Int32[3, 17] 0.0
2 2601 Int32[3, 17] 0.0
3 23409 Int32[3, 17] 0.0
4 153 Int32[3, 17] 0.0
5 459 Int32[3, 17] 0.0
6 867 Int32[3, 17] 0.0
7 1377 Int32[3, 17] 0.0
8 4131 Int32[3, 17] 0.0
9 7803 Int32[3, 17] 0.0
10 12393 Int32[3, 17] 0.0
11 14739 Int32[3, 17] 0.0
12 37179 Int32[3, 17] 0.0

Result list for num: 1000, factors: Int32[2, 5]

nn num factors dist
1 800 Int32[2, 5] 0.0
2 10 Int32[2, 5] 0.0
3 20 Int32[2, 5] 0.0
4 40 Int32[2, 5] 0.0
5 50 Int32[2, 5] 0.0
6 80 Int32[2, 5] 0.0
7 100 Int32[2, 5] 0.0
8 160 Int32[2, 5] 0.0
9 200 Int32[2, 5] 0.0
10 250 Int32[2, 5] 0.0
11 320 Int32[2, 5] 0.0
12 400 Int32[2, 5] 0.0

Result list for num: 1492, factors: Int32[2, 373]

nn num factors dist
1 11936 Int32[2, 373] 0.0
2 23872 Int32[2, 373] 0.0
3 47744 Int32[2, 373] 0.0
4 746 Int32[2, 373] 0.0
5 1492 Int32[2, 373] 0.0
6 2984 Int32[2, 373] 0.0
7 5968 Int32[2, 373] 0.0
8 95488 Int32[2, 373] 0.0
9 2238 Int32[2, 3, 373] 0.2
10 10444 Int32[2, 7, 373] 0.2
11 9698 Int32[2, 13, 373] 0.2
12 17158 Int32[2, 23, 373] 0.2

Result list for num: 3192, factors: Int32[2, 3, 7, 19]

nn num factors dist
1 798 Int32[2, 3, 7, 19] 0.0
2 1596 Int32[2, 3, 7, 19] 0.0
3 2394 Int32[2, 3, 7, 19] 0.0
4 3192 Int32[2, 3, 7, 19] 0.0
5 4788 Int32[2, 3, 7, 19] 0.0
6 5586 Int32[2, 3, 7, 19] 0.0
7 6384 Int32[2, 3, 7, 19] 0.0
8 7182 Int32[2, 3, 7, 19] 0.0
9 9576 Int32[2, 3, 7, 19] 0.0
10 11172 Int32[2, 3, 7, 19] 0.0
11 12768 Int32[2, 3, 7, 19] 0.0
12 14364 Int32[2, 3, 7, 19] 0.0

All-kNN and recall evaluation

allknn computes the exact kNN for every item in the dataset. Here we compare the approximate SearchGraph result against ExhaustiveSearch to measure recall.

k = 10

# Exact baseline (only feasible on a small sample for demo purposes)
sample_n = 3_000
sample_idx = randperm(n + 1)[1:sample_n]
db_sample  = SubDatabase(db, sample_idx)

exact_idx = ExhaustiveSearch(dist, db_sample)
exact_ctx = GenericContext()
gold_ids, gold_dists = allknn(exact_idx, exact_ctx, k)

# Approximate with SearchGraph built on the same sample
G_sample   = SearchGraph(dist, db_sample)
ctx_sample = SearchGraphContext(hyperparameters_callback=OptimizeParameters(MinRecall(0.95)))
index!(G_sample, ctx_sample)
approx_ids, _ = allknn(G_sample, ctx_sample, k)

recall = macrorecall(gold_ids, approx_ids)
@info "All-kNN recall: $(round(recall, digits=4))"

UMAP visualization

e2, e3 = let min_dist=0.5f0, k=20, n_epochs=75, neg_sample_rate=3, tol=1e-3,
             layout=SpectralLayout()
    @time "2D UMAP" U2 = fit(UMAP, G; k, neg_sample_rate, layout, n_epochs, tol, min_dist)
    @time "3D UMAP" U3 = fit(U2, 3; neg_sample_rate, n_epochs, tol)
    @time "predict 2D" e2 = clamp.(predict(U2), -10f0, 10f0)
    @time "predict 3D" e3 = clamp.(predict(U3), -10f0, 10f0)
    e2, e3
end
function normcolors(V)
    mn, mx = extrema(V)
    @. V = clamp((V - mn) / (mx - mn), 0f0, 1f0)
end

normcolors(@view e3[1, :])
normcolors(@view e3[2, :])
normcolors(@view e3[3, :])

let C = [RGB(c[1], c[2], c[3]) for c in eachcol(e3)],
    X = view(e2, 1, :), Y = view(e2, 2, :)
    scatter(X, Y; color=C, fmt=:png, alpha=0.2, size=(600, 600),
            ma=0.3, ms=2, msw=0, label="",
            yticks=nothing, xticks=nothing, xaxis=false, yaxis=false,
            title="Prime factors (n=100k) — UMAP coloured by 3D embedding")
end
plot!()

Environment and dependencies

Julia Version 1.12.7
Commit 6d172b025e4 (2026-08-15 08:05 UTC)
Build Info:
  Official https://julialang.org release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 64 × Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, cascadelake)
  GC: Built with stock GC
Threads: 64 default, 1 interactive, 64 GC (on 64 virtual cores)
Environment:
  JULIA_PROJECT = @.
  JULIA_NUM_THREADS = auto
  JULIA_LOAD_PATH = @:@stdlib
Status `~/Research/SimilaritySearchDemos/Project.toml`
  [aaaa29a8] Clustering v0.15.8
  [944b1d66] CodecZlib v0.7.9
  [a93c6f00] DataFrames v1.8.2
  [f67ccb44] HDF5 v0.17.3
  [0f8b85d8] JSON3 v1.14.3
  [23fbe1c1] Latexify v0.16.12
  [eb30cadb] MLDatasets v0.7.21
  [06eb3307] ManifoldLearning v0.9.0
⌅ [ca7969ec] PlotlyLight v0.11.1
  [91a5bcdd] Plots v1.41.7
  [27ebfcd6] Primes v0.5.7
  [92933f4c] ProgressMeter v1.11.0
  [ca7ab67e] SimSearchManifoldLearning v0.4.0 `../SimSearchManifoldLearning.jl`
  [053f045d] SimilaritySearch v1.2.0 `../SimilaritySearch.jl`
⌅ [2913bbd2] StatsBase v0.33.21
  [f3b207a7] StatsPlots v0.15.8
  [7f6f6c8a] TextSearch v1.1.1 `../TextSearch.jl`
Info Packages marked with ⌅ have new versions available but compatibility constraints restrict them from upgrading. To see why use `status --outdated`