A101296 n has the a(n)-th distinct prime signature.

1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 5, 6, 2, 9, 2, 10, 4, 4, 4, 11, 2, 4, 4, 8, 2, 9, 2, 6, 6, 4, 2, 12, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 13, 2, 4, 6, 14, 4, 9, 2, 6, 4, 9, 2, 15, 2, 4, 6, 6, 4, 9, 2, 12, 7, 4, 2, 13, 4, 4, 4, 8, 2, 13, 4, 6, 4, 4, 4, 16, 2, 6, 6, 11, 2, 9, 2, 8, 9, 4, 2, 15, 2, 9, 4, 12, 2, 9, 4, 6, 6, 4, 4, 17

Offset

1,2

Comments

From Antti Karttunen, May 12 2017: (Start)

Restricted growth sequence transform of A046523, the least representative of each prime signature. Thus this partitions the natural numbers to the same equivalence classes as A046523, i.e., for all i, j: a(i) = a(j) <=> A046523(i) = A046523(j), and for that reason satisfies in that respect all the same conditions as A046523. For example, we have, for all i, j: if a(i) = a(j), then:

A000005(i) = A000005(j), A008683(i) = A008683(j), A286605(i) = A286605(j).

So, this sequence (instead of A046523) can be used for finding sequences where a(n)'s value is dependent only on the prime signature of n, that is, only on the multiset of prime exponents in the factorization of n. (End)

This is also the restricted growth sequence transform of many other sequences, for example, that of A181819. See further comments there. - Antti Karttunen, Apr 30 2022

Links

Michel Marcus (terms 1..10000) & Antti Karttunen, Table of n, a(n) for n = 1..100000

Formula

A025487(a(n)) = A046523(n).

Indices of records give A025487. - Michel Marcus, Nov 16 2015

From David A. Corneth, May 12 2017: (Start) [Corresponding characteristic function in brackets]

a(A000012(n)) = 1 (sig.: ()). [A063524]

a(A000040(n)) = 2 (sig.: (1)). [A010051]

a(A001248(n)) = 3 (sig.: (2)). [A302048]

a(A006881(n)) = 4 (sig.: (1,1)). [A280710]

a(A030078(n)) = 5 (sig.: (3)).

a(A054753(n)) = 6 (sig.: (1,2)). [A353472]

a(A030514(n)) = 7 (sig.: (4)).

a(A065036(n)) = 8 (sig.: (1,3)).

a(A007304(n)) = 9 (sig.: (1,1,1)). [A354926]

a(A050997(n)) = 10 (sig.: (5)).

a(A085986(n)) = 11 (sig.: (2,2)).

a(A178739(n)) = 12 (sig.: (1,4)).

a(A085987(n)) = 13 (sig.: (1,1,2)).

a(A030516(n)) = 14 (sig.: (6)).

a(A143610(n)) = 15 (sig.: (2,3)).

a(A178740(n)) = 16 (sig.: (1,5)).

a(A189975(n)) = 17 (sig.: (1,1,3)).

a(A092759(n)) = 18 (sig.: (7)).

a(A189988(n)) = 19 (sig.: (2,4)).

a(A179643(n)) = 20 (sig.: (1,2,2)).

a(A189987(n)) = 21 (sig.: (1,6)).

a(A046386(n)) = 22 (sig.: (1,1,1,1)).

a(A162142(n)) = 23 (sig.: (2,2,2)).

a(A179644(n)) = 24 (sig.: (1,1,4)).

a(A179645(n)) = 25 (sig.: (8)).

a(A179646(n)) = 26 (sig.: (2,5)).

a(A163569(n)) = 27 (sig.: (1,2,3)).

a(A179664(n)) = 28 (sig.: (1,7)).

a(A189982(n)) = 29 (sig.: (1,1,1,2)).

a(A179666(n)) = 30 (sig.: (3,4)).

a(A179667(n)) = 31 (sig.: (1,1,5)).

a(A179665(n)) = 32 (sig.: (9).

a(A189990(n)) = 33 (sig.: (2,6)).

a(A179669(n)) = 34 (sig.: (1,2,4)).

a(A179668(n)) = 35 (sig.: (1,8)).

a(A179670(n)) = 36 (sig.: (1,1,1,3)).

a(A179671(n)) = 37 (sig.: (3,5)).

a(A162143(n)) = 38 (sig.: (2,2,2)).

a(A179672(n)) = 39 (sig.: (1,1,6)).

a(A030629(n)) = 40 (sig.: (10)).

a(A179688(n)) = 41 (sig.: (1,3,3)).

a(A179689(n)) = 42 (sig.: (2,7)).

a(A179690(n)) = 43 (sig.: (1,1,2,2)).

a(A189991(n)) = 44 (sig.: (4,4)).

a(A179691(n)) = 45 (sig.: (1,2,5)).

a(A179692(n)) = 46 (sig.: (1,9)).

a(A179693(n)) = 47 (sig.: (1,1,1,4)).

a(A179694(n)) = 48 (sig.: (3,6)).

a(A179695(n)) = 49 (sig.: (2,2,3)).

a(A179696(n)) = 50 (sig.: (1,1,7)).

(End)

Example

From David A. Corneth, May 12 2017: (Start)
1 has prime signature (), the first distinct prime signature. Therefore, a(1) = 1.
2 has prime signature (1), the second distinct prime signature after (1). Therefore, a(2) = 2.
3 has prime signature (1), as does 2. Therefore, a(3) = a(2) = 2.
4 has prime signature (2), the third distinct prime signature after () and (1). Therefore, a(4) = 3. (End)
From Antti Karttunen, May 12 2017: (Start)
Construction of restricted growth sequences: In this case we start with a(1) = 1 for A046523(1) = 1, and thereafter, for all n > 1, we use the least so far unused natural number k for a(n) if A046523(n) has not been encountered before, otherwise [whenever A046523(n) = A046523(m), for some m < n], we set a(n) = a(m).
For n = 2, A046523(2) = 2, which has not been encountered before (first prime), thus we allot for a(2) the least so far unused number, which is 2, thus a(2) = 2.
For n = 3, A046523(2) = 2, which was already encountered as A046523(1), thus we set a(3) = a(2) = 2.
For n = 4, A046523(4) = 4, not encountered before (first square of prime), thus we allot for a(4) the least so far unused number, which is 3, thus a(4) = 3.
For n = 5, A046523(5) = 2, as for the first time encountered at n = 2, thus we set a(5) = a(2) = 2.
For n = 6, A046523(6) = 6, not encountered before (first semiprime pq with distinct p and q), thus we allot for a(6) the least so far unused number, which is 4, thus a(6) = 4.
For n = 8, A046523(8) = 8, not encountered before (first cube of a prime), thus we allot for a(8) the least so far unused number, which is 5, thus a(8) = 5.
For n = 9, A046523(9) = 4, as for the first time encountered at n = 4, thus a(9) = 3.
(End)
From David A. Corneth, May 12 2017: (Start)
(Rough) description of an algorithm of computing the sequence:
Suppose we want to compute a(n) for n in [1..20].
We set up a vector of 20 elements, values 0, and a number m = 1, the minimum number we haven't checked and c = 0, the number of distinct prime signatures we've found so far.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
We check the prime signature of m and see that it's (). We increase c with 1 and set all elements up to 20 with prime signature () to 1. In the process, we adjust m. This gives:
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The least number we haven't checked is m = 2. 2 has prime signature (1). We increase c with 1 and set all elements up to 20 with prime signature (1) to 2. In the process, we adjust m. This gives:
[1, 2, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
We check the prime signature of m = 4 and see that its prime signature is (2). We increase c with 1 and set all numbers up to 20 with prime signature (2) to 3. This gives:
[1, 2, 2, 3, 2, 0, 2, 0, 3, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
Similarily, after m = 6, we get
[1, 2, 2, 3, 2, 4, 2, 0, 3, 4, 2, 0, 2, 4, 4, 0, 2, 0, 2, 0], after m = 8 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 0, 2, 4, 4, 0, 2, 0, 2, 0], after m = 12 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 0, 2, 6, 2, 0], after m = 16 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 0], after m = 20 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 8]. Now, m > 20 so we stop. (End)
The above method is inefficient, because the step "set all elements a(n) up to n = Nmax with prime signature s(n) = S[c] to c" requires factoring all integers up to Nmax (or at least comparing their signature, once computed, with S[c]) again and again. It is much more efficient to run only once over each m = 1..Nmax, compute its prime signature s(m), add it to an ordered list in case it did not occur earlier, together with its "rank" (= new size of the list), and assign that rank to a(m). The list of prime signatures is much shorter than [1..Nmax]. One can also use m'(m) := the smallest n with the prime signature of m (which is faster to compute than to search for the signature) as representative for s(m), and set a(m) := a(m'(m)). Then it is sufficient to have just one counter (number of prime signatures seen so far) as auxiliary variable, in addition to the sequence to be computed. - M. F. Hasler, Jul 18 2019

Maple

A101296 := proc(n)
    local a046523, a;
    a046523 := A046523(n) ;
    for a from 1 do
        if A025487(a) = a046523 then
            return a;
        elif A025487(a) > a046523 then
            return -1 ;
        end if;
    end do:
end proc: # R. J. Mathar, May 26 2017

Mathematica

With[{nn = 120}, Function[s, Table[Position[Keys@s, k_ /; MemberQ[k, n]][[1, 1]], {n, nn}]]@ Map[#1 -> #2 & @@ # &, Transpose@ {Values@ #, Keys@ #}] &@ PositionIndex@ Table[Times @@ MapIndexed[Prime[First@ #2]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]] - Boole[n == 1], {n, nn}] ] (* Michael De Vlieger, May 12 2017, Version 10 *)

Prog

(PARI) find(ps, vps) = {for (k=1, #vps, if (vps[k] == ps, return(k)); ); }
lisps(nn) = {vps = []; for (n=1, nn, ps = vecsort(factor(n)[, 2]); ips = find(ps, vps); if (! ips, vps = concat(vps, ps); ips = #vps); print1(ips, ", "); ); } \\ Michel Marcus, Nov 15 2015; edited by M. F. Hasler, Jul 16 2019
(PARI)
rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences, invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences, invec[i], i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset, vec, bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
write_to_bfile(1, rgs_transform(vector(100000, n, A046523(n))), "b101296.txt");
\\ Antti Karttunen, May 12 2017

Crossrefs

Cf. A025487, A046523, A064839 (ordinal transform of this sequence), A181819, and arrays A095904, A179216.

Cf. A000005, A008683.

Sequences that are unions of finite number (>= 2) of equivalence classes determined by the values that this sequence obtains (i.e., sequences mentioned in David A. Corneth's May 12 2017 formula): A001358 (A001248 U A006881, values 3 & 4), A007422 (values 1, 4, 5), A007964 (2, 3, 4, 5), A014612 (5, 6, 9), A030513 (4, 5), A037143 (1, 2, 3, 4), A037144 (1, 2, 3, 4, 5, 6, 9), A080258 (6, 7), A084116 (2, 4, 5), A167171 (2, 4), A217856 (6, 9).

Cf. also A077462, A305897 (stricter variants, with finer partitioning) and A254524, A286603, A286605, A286610, A286619, A286621, A286622, A286626, A286378 for other similarly constructed sequences.

Sequence in context: A338138 A369760 A305899 * A305898 A181819 A302046

Adjacent sequences: A101293 A101294 A101295 * A101297 A101298 A101299

Keyword

easy,nonn

Author

David Wasserman, Dec 21 2004

Extensions

Data section extended to 120 terms by Antti Karttunen, May 12 2017

Minor edits/corrections by M. F. Hasler, Jul 18 2019

Status

approved