A064839 List the natural numbers starting a new row only with each new least prime signature (A025487). a(n) is the column position associated with n.

1, 1, 2, 1, 3, 1, 4, 1, 2, 2, 5, 1, 6, 3, 4, 1, 7, 2, 8, 3, 5, 6, 9, 1, 3, 7, 2, 4, 10, 1, 11, 1, 8, 9, 10, 1, 12, 11, 12, 2, 13, 2, 14, 5, 6, 13, 15, 1, 4, 7, 14, 8, 16, 3, 15, 4, 16, 17, 17, 1, 18, 18, 9, 1, 19, 3, 19, 10, 20, 4, 20, 1, 21, 21, 11, 12, 22, 5, 22, 2, 2, 23, 23, 2, 24, 25, 26

Offset: 1

Author

Alford Arnold, Oct 24 2001

Keywords

• easy
• nice
• nonn

Comments

Row 2 records the primes (A000040). Rows 3 and 4 record the semiprimes (A001358). Rows 5, 6 and 9 record the 3-almost primes (A014612) etc. A058933 is a similar sequence based on k-almost primes.

The graph of this sequence is interesting for large n because it shows multiple curves, one for each prime signature. For example, the six highest curves on the graph of a(n) for n up to 10^4 are for the (1,1), (1,1,1), (1), (2,1,1), (2,1), and (1,1,1,1) prime signatures. The (1) curve dominates until n=58; the (1,1) curve dominates until n=1279786, when the (1,1,1) curve intersects the (1,1) curve. Each (1,1,...,1) curve dominates for a finite number of n.

Ordinal transform of A101296. - Antti Karttunen, May 15 2017

a(n) is the number of positive integers up to n with the same prime signature as n. For example, the a(20) = 3 numbers are {12, 18, 20}. - Gus Wiseman, Jul 08 2019

Ordinal transform of A046523. - Alois P. Heinz, May 31 2020

Examples

			The list begins as follows:
1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 ...
4 9 25 49 ...
6 10 14 15 21 22 26 33 34 35 38 39 46 51 ...
8 27 ...
12 18 20 28 44 45 50 52 ...
16 ...
Note: the above array, without the initial 1, is given by A095904 (and its transpose A179216). - _Antti Karttunen_, May 15 2017
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000040, A001358, A014612, A025487, A046523, A058933, A101296.

Cf. also arrays A095904, A179216.

Cf. A001222, A085089, A118914, A124010, A325263, A325365, A326438, A326439.

Programs

Maple

p:= proc() 0 end:
a:= proc(n) option remember; local t; a(n-1);
      t:= (l-> mul(ithprime(i)^l[i], i=1..nops(l)))(
           sort(map(i-> i[2], ifactors(n)[2]), `>`));
      p(t):= p(t)+1
    end: a(0):=0:
seq(a(n), n=1..100);  # Alois P. Heinz, May 31 2020

Mathematica

prisig[n_]:=If[n==1,{},Sort[Last/@FactorInteger[n]]];
Table[Count[Array[prisig,n],prisig[n]],{n,30}] (* Gus Wiseman, Jul 08 2019 *)

Extensions

More terms from Naohiro Nomoto, Oct 31 2001