Menu

A fun little exploration on the combinatorial structure of primes

#math#redditmath#multisets#empty#prime
Reading 0:00
15s threshold

Lately I've been enjoying exploring the connections between algebra in the natural numbers and combinatorics. It's a really rich vein of mathematics to play with and even though it's not an area of math I've studied formally I'm constantly surprised that I haven't heard of some of the patterns I've spotted.

I wanted to share an algorithm I found that lists out prime factors of the natural numbers sequentially without using any algebra. I'm not sure how interesting it is as it's all derived from basic observations about primes but it's nifty nonetheless.

-----

Setup:

Start with a list L with an empty multiset L= [{}] and k = 0.

Iteration:

Take a copy of the L and reverse it for Lr, pair up the multisets in Lr with the multisets of L in order (the nth multi set of each list paired up).

Take the multiset union M of all the multisets of Lr that are sub multisets of the multisets in L which they are paired with.

If M is empty, increment k by 1 and add the multiset {k} the back of L.

If M is non empty but…

Continue reading — create a free account

Join HashtagPLUS to read full articles, follow hashtags, vote, and join the conversation.