We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Jelly, 9 bytes

ÆṪÐL·ÆFL€S

Try it online! or verify all test cases.

Background

The definition of sequence A064097 implies that

definition

By Euler's product formula

Euler's product formula

where φ denotes Euler's totient function and p varies only over prime numbers.

Combining both, we deduce the property

first property

where ω denotes the number of distinct prime factors of n.

Applying the formula k times, where k is large enough so that φ^k(n) = 1, we get

second property

From this property, we obtain the formula

formula

where the last equality holds because ω(1) = 0.

How it works

ÆṪÐL·ÆFL€S Main link. Argument: n
 ÐL· Repeatedly apply the link to the left until the results are no longer
 unique, and return the list of unique results.
ÆṪ Apply Euler's totient function.
 Since φ(1) = 1, This computes φ-towers until 1 is reached.
 ÆF Break each resulting integer into [prime, exponent] pairs.
 L€ Compute the length of each list.
 This counts the number of distinct prime factors.
 S Add the results.