cp's OEIS Frontend

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

%I A344844 #54 Apr 19 2025 18:01:11
%S A344844 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,
%T A344844 28,42,63,70,105,175,98,147,245,343,16,24,36,54,81,40,60,90,135,100,
%U A344844 150,225,250,375,625,56,84,126,189,140,210,315,350,525,875,196,294,441
%N A344844 A prime-factor-based permutation of the positive integers, based on a recursive definition (see Comments for the algorithm).
%C A344844 Algorithm:
%C A344844 Definitions:
%C A344844 K = the index of the largest prime that has appeared.
%C A344844 L = the index of the smallest prime factor of a(n-1).
%C A344844 M = the multiplicity of prime(L) within a(n-1).
%C A344844 Rules:
%C A344844 1. a(1) = 1. (K is considered to be 0.)
%C A344844 2. If a(n-1) = prime(K)^K, then a(n) = prime(K+1).
%C A344844 3. If a(n-1) = prime(K)^(K-1), then a(n) = 2^K.
%C A344844 4. If a(n-1) = prime(K)^i, such that I < (K-1), then a(n) = prime(K)*2^i.
%C A344844 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.
%C A344844 Explanation:
%C A344844 This sequence gives priority to smaller primes and smaller powers of primes, while also containing every positive integer exactly once.
%C A344844 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.
%C A344844 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.
%C A344844 This sequence, when plotted, produces a fractal of increasing detail, which recurs at each new prime.
%C A344844 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.
%H A344844 Hugo Pfoertner, <a href="/A344844/b344844.txt">Table of n, a(n) for n = 1..10000</a>
%H A344844 Hugo Pfoertner, <a href="/A344844/a344844.png">Illustration of first 2500 terms</a>, (2021).
%H A344844 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A344844 a(2)=2:
%e A344844    2 is the most recent prime in the sequence.
%e A344844    The prime index of 2 is 1.
%e A344844    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.
%e A344844    ;a(3)=3.
%e A344844 a(3)=3:
%e A344844    3 is the most recent prime in the sequence.
%e A344844    The prime index of 3 is 2.
%e A344844    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.
%e A344844    ;a(4)=4.
%e A344844 a(4)=4:
%e A344844    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.
%e A344844    ;a(5)=6.
%e A344844 a(6)=9:
%e A344844    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.
%e A344844   ;a(7)=5.
%e A344844 a(7)=5:
%e A344844    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.
%e A344844    ;a(8)=10.
%o A344844 (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<<mrprimeind; next(1) ); res[i] = mrprime*2^e , f = factor(res[i-1]); e = f[1, 2]; c = 1<<(e-1) * nextprime(f[1, 1] + 1); f[1, 2] = 0; res[i] = factorback(f)*c; ) ); res } \\ _David A. Corneth_, Jan 01 2021
%o A344844 (Python)
%o A344844 from math import prod
%o A344844 from sympy import nextprime
%o A344844 from itertools import count, islice, combinations_with_replacement as cwr
%o A344844 def agen(): # generator of terms
%o A344844     aset, plst = set(), [1, 2]
%o A344844     for n in count(1):
%o A344844         row = []
%o A344844         for mc in cwr(plst, n):
%o A344844             p = prod(mc)
%o A344844             if p not in aset:
%o A344844                 row.append((n-mc.count(1), mc[::-1], p))
%o A344844                 aset.add(p)
%o A344844         plst.append(nextprime(plst[-1]))
%o A344844         yield from (p for m, mcrev, p in sorted(row))
%o A344844 print(list(islice(agen(), 80))) # _Michael S. Branicky_, Apr 19 2025
%Y A344844 Cf. A108644.
%K A344844 nonn
%O A344844 1,2
%A A344844 _Elliott Sanders_, May 29 2021