A344844 A prime-factor-based permutation of the positive integers, based on a recursive definition (see Comments for the algorithm).

1, 2, 3, 4, 6, 9, 5, 10, 15, 25, 8, 12, 18, 27, 20, 30, 45, 50, 75, 125, 7, 14, 21, 35, 49, 28, 42, 63, 70, 105, 175, 98, 147, 245, 343, 16, 24, 36, 54, 81, 40, 60, 90, 135, 100, 150, 225, 250, 375, 625, 56, 84, 126, 189, 140, 210, 315, 350, 525, 875, 196, 294, 441

Offset: 1

Author

Elliott Sanders, May 29 2021

Keywords

• nonn

Comments

Algorithm:

Definitions:

K = the index of the largest prime that has appeared.

L = the index of the smallest prime factor of a(n-1).

M = the multiplicity of prime(L) within a(n-1).

Rules:

1. a(1) = 1. (K is considered to be 0.)

2. If a(n-1) = prime(K)^K, then a(n) = prime(K+1).

3. If a(n-1) = prime(K)^(K-1), then a(n) = 2^K.

4. If a(n-1) = prime(K)^i, such that I < (K-1), then a(n) = prime(K)*2^i.

5. If a(n-1) is not a power of prime(K), then a(n) = a(n-1)*2^(M-1)*prime(L+1)/prime(L)^M.

Explanation:

This sequence gives priority to smaller primes and smaller powers of primes, while also containing every positive integer exactly once.

The order in which the numbers appear is according to the multiplicity of each of their distinct prime factors. Numbers with smaller prime factors and a smaller number of prime factors, counted with multiplicity, appear earlier in the sequence.

In the traditional counting of the positive integers, 1 is added each time. This allows for additive simplicity, but not multiplicative simplicity. In this sequence, the combinations of prime factors "climb up" by taking one from the exponent of the smallest prime factor and giving it to the exponent of the next larger prime.

This sequence, when plotted, produces a fractal of increasing detail, which recurs at each new prime.

If you count the successive terms of this sequence which vary neither in their largest prime factor "h" nor their number of prime factors (counted with multiplicity) "f", and write out each number in an f X h table, it will construct Pascal's Triangle along an L-shaped serpentine path, identical to the path of A108644 tabled as a square array.

Examples

			a(2)=2:
   2 is the most recent prime in the sequence.
   The prime index of 2 is 1.
   a(2) is the most recent prime in the sequence to the power of its own prime index. Thus, apply Rule 1. a(3) will be the next prime.
   ;a(3)=3.
a(3)=3:
   3 is the most recent prime in the sequence.
   The prime index of 3 is 2.
   a(3) is the most recent prime in the sequence (3) to a power that is 1 less than its prime index (2). Thus, apply Rule 2. a(4) will be 2 to the power of the prime index of 3, or 4.
   ;a(4)=4.
a(4)=4:
   4 is not a power of the most recent prime in the sequence (3). Thus, apply Rule 4. The non-unique prime factors of 4 are 2 with a multiplicity of 2. Subtract 1 from that multiplicity and make it the new multiplicity of 2, and then add 1 to the multiplicity of the next prime up. So the multiplicity of 2 goes down to 1 and the multiplicity of 3 goes up to 1.
   ;a(5)=6.
a(6)=9:
   9 is the most recent prime in the sequence (3) to the power of its own prime index (2). Thus, apply Rule 1. a(7) will be the next prime.
  ;a(7)=5.
a(7)=5:
   5 is the most recent prime in the sequence to the power of 1, which is 2 less than its prime index (3). Thus, apply Rule 3. a(8) will thus be 5 times 2 to the power of 1.
   ;a(8)=10.
		

Links

• Hugo Pfoertner, Table of n, a(n) for n = 1..10000
• Hugo Pfoertner, Illustration of first 2500 terms, (2021).
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A108644.

Programs

PARI

first(n) = { n = max(n, 2); res = vector(n); res[1] = 1; res[2] = 2; mrprime = 2; mrprimeind = 1; for(i = 3, n, e = logint(res[i-1], mrprime); if(mrprime ^ e == res[i-1], if(e == mrprimeind, res[i] = nextprime(mrprime + 1); mrprime = res[i]; mrprimeind++; next(1); ); if(e == mrprimeind - 1, res[i] = 1<David A. Corneth, Jan 01 2021

Python

from math import prod
from sympy import nextprime
from itertools import count, islice, combinations_with_replacement as cwr
def agen(): # generator of terms
    aset, plst = set(), [1, 2]
    for n in count(1):
        row = []
        for mc in cwr(plst, n):
            p = prod(mc)
            if p not in aset:
                row.append((n-mc.count(1), mc[::-1], p))
                aset.add(p)
        plst.append(nextprime(plst[-1]))
        yield from (p for m, mcrev, p in sorted(row))
print(list(islice(agen(), 80))) # Michael S. Branicky, Apr 19 2025