factor_summary

std.elementwise.factor_summary · Level L4

Trial division of each n ≥ 1, and four facts read from it: the smallest prime factor (0 for n = 1), ω(n), the number of distinct primes, whether n is squarefree, and Euler's φ(n). A While over trial_step that tries 2 and then odd d up to √n; what remains above 1 at the end is one more prime. The reference factors each n independently.

n = Π pᵢ^eᵢ: spf = min pᵢ, ω = #{pᵢ}, squarefree ⇔ all eᵢ = 1, φ = n·Π(1 − 1/pᵢ)

Signature

factor_summary(n: i64[s]) → i64[s], i64[s], i64[s], i64[s]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference factor n by trial division; read off min p, #distinct p, all exponents 1, n·Π(1 − 1/p) in exact rational arithmetic, on all 40 test cases.
All 652 int64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the int64 nearest the exact value): 100%
bit-equal to the NumPy formula in int64: 100%
largest error, in units in the last place: 0

Note

About √n/2 steps: for n up to 10⁹ that is up to 16,000 steps. max_steps is 10⁵. The verification uses n up to 10⁵.

Identity

Calls

trial_running trial_step

Called by

is_prime mobius smallest_prime_factor totient

sha256:cdf3f8640f4a692f3854673745d8f33b4d62f579ee2a25d38742330f6432dd29

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.elementwise.factor_summary · Ω:factor_summary
Pins: sha256:07018931268b835f21468be42f2865d4710b7feabb8f6276a1cdacefa56ee88athis graph and the 2 it reaches through calls
Evidence: sha256:5f1ac294599f871245954891f5a6bf9c511de0f5323928e98f2a5515beb5f3b9the hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.