%I
%S 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,
%T 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,
%U 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
%N n has the a(n)th distinct prime signature.
%C From _Antti Karttunen_, May 12 2017: (Start)
%C Restricted growth sequence 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:
%C For all i, j: a(i) = a(j) => A000005(i) = A000005(j).
%C For all i, j: a(i) = a(j) => A008683(i) = A008683(j).
%C For all i, j: a(i) = a(j) => A286605(i) = A286605(j).
%C 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.
%C (End)
%H Michel Marcus (terms 1..10000) & Antti Karttunen, <a href="/A101296/b101296.txt">Table of n, a(n) for n = 1..100000</a>
%F A025487(a(n)) = A046523(n).
%F Indices of records give A025487.  _Michel Marcus_, Nov 16 2015
%F From _David A. Corneth_, May 12 2017: (Start)
%F a(A000012(n)) = 1 (sig.: ()).
%F a(A000040(n)) = 2 (sig.: (1)).
%F a(A001248(n)) = 3 (sig.: (2)).
%F a(A006881(n)) = 4 (sig.: (1,1)).
%F a(A030078(n)) = 5 (sig.: (3)).
%F a(A054753(n)) = 6 (sig.: (1,2)).
%F a(A030514(n)) = 7 (sig.: (4)).
%F a(A065036(n)) = 8 (sig.: (1,3)).
%F a(A007304(n)) = 9 (sig.: (1,1,1)).
%F a(A050997(n)) = 10 (sig.: (5)).
%F a(A085986(n)) = 11 (sig.: (2,2)).
%F a(A178739(n)) = 12 (sig.: (1,4)).
%F a(A085987(n)) = 13 (sig.: (1,1,2)).
%F a(A030516(n)) = 14 (sig.: (6)).
%F a(A143610(n)) = 15 (sig.: (2,3)).
%F a(A178740(n)) = 16 (sig.: (1,5)).
%F a(A189975(n)) = 17 (sig.: (1,1,3)).
%F a(A092759(n)) = 18 (sig.: (7)).
%F a(A189988(n)) = 19 (sig.: (2,4)).
%F a(A179643(n)) = 20 (sig.: (1,2,2)).
%F a(A189987(n)) = 21 (sig.: (1,6)).
%F a(A046386(n)) = 22 (sig.: (1,1,1,1)).
%F a(A162142(n)) = 23 (sig.: (2,2,2)).
%F a(A179644(n)) = 24 (sig.: (1,1,4)).
%F a(A179645(n)) = 25 (sig.: (8)).
%F a(A179646(n)) = 26 (sig.: (2,5)).
%F a(A163569(n)) = 27 (sig.: (1,2,3)).
%F a(A179664(n)) = 28 (sig.: (1,7)).
%F a(A189982(n)) = 29 (sig.: (1,1,1,2)).
%F a(A179666(n)) = 30 (sig.: (3,4)).
%F a(A179667(n)) = 31 (sig.: (1,1,5)).
%F a(A179665(n)) = 32 (sig.: (9).
%F a(A189990(n)) = 33 (sig.: (2,6)).
%F a(A179669(n)) = 34 (sig.: (1,2,4)).
%F a(A179668(n)) = 35 (sig.: (1,8)).
%F a(A179670(n)) = 36 (sig.: (1,1,1,3)).
%F a(A179671(n)) = 37 (sig.: (3,5)).
%F a(A162143(n)) = 38 (sig.: (2,2,2)).
%F a(A179672(n)) = 39 (sig.: (1,1,6)).
%F a(A030629(n)) = 40 (sig.: (10)).
%F a(A179688(n)) = 41 (sig.: (1,3,3)).
%F a(A179689(n)) = 42 (sig.: (2,7)).
%F a(A179690(n)) = 43 (sig.: (1,1,2,2)).
%F a(A189991(n)) = 44 (sig.: (4,4)).
%F a(A179691(n)) = 45 (sig.: (1,2,5)).
%F a(A179692(n)) = 46 (sig.: (1,9)).
%F a(A179693(n)) = 47 (sig.: (1,1,1,4)).
%F a(A179694(n)) = 48 (sig.: (3,6)).
%F a(A179695(n)) = 49 (sig.: (2,2,3)).
%F a(A179696(n)) = 50 (sig.: (1,1,7)).
%F (End)
%e From _David A. Corneth_, May 12 2017: (Start)
%e 1 has prime signature (), the first distinct prime signature. Therefore, a(1) = 1.
%e 2 has prime signature (1), the second distinct prime signature after (1). Therefore, a(2) = 2.
%e 3 has prime signature (1), as does 2. Therefore, a(3) = a(2) = 2.
%e 4 has prime signature (2), the third distinct prime signature after () and (1). Therefore, a(4) = 1. (End)
%e From _Antti Karttunen_, May 12 2017: (Start)
%e Construction of rectricted growth sequences: In this case we start with a(1)=1 for A046523(1)=1, and then after, 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).
%e 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.
%e For n=3, A046523(2) = 2, which was already encountered as A046523(1), thus we set a(3) = a(2) = 2.
%e 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.
%e For n=5, A046523(5) = 2, which was for the first time encountered at n=2, thus we set a(5) = 2.
%e 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.
%e For n=8, A046523(8) = 8, not encountered before (first cube of prime), thus we allot for a(8) the least so far unused number, which is 5, thus a(8) = 5.
%e For n=9, A046523(9) = 4, which was for the first time encountered at n=4, thus a(9) = 3.
%e (End)
%e From _David A. Corneth_, May 12 2017 (Start):
%e (Rough) description of an algorithm of computing the sequence:
%e Suppose we want to compute a(n) for n in [1..20].
%e 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.
%e [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
%e 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:
%e [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:
%e [1, 2, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
%e We check the prime signature of m = 4 and see that it's prime signature is (2). We increase c with 1 and set all numbers up to 20 with prime signature (2) to 3. This gives:
%e [1, 2, 2, 3, 2, 0, 2, 0, 3, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
%e Similarily, after m = 6, we get
%e [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:
%e [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:
%e [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:
%e [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:
%e [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)
%p A101296 := proc(n)
%p local a046523, a;
%p a046523 := A046523(n) ;
%p for a from 1 do
%p if A025487(a) = a046523 then
%p return a;
%p elif A025487(a) > a046523 then
%p return 1 ;
%p end if;
%p end do:
%p end proc: # _R. J. Mathar_, May 26 2017
%t 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 *)
%o (PARI) find(ps, vps) = {for (k=1, #vps, if (vps[k] == ps, return(k)););}
%o add(vps, ps) = {nvps = vector(#vps+1); for (k=1, #vps, nvps[k] = vps[k]); nvps[#vps+1] = ps; nvps;}
%o lisps(nn) = {vps = []; for (n=1, nn, ps = vecsort(factor(n)[,2]); ips = find(ps, vps); if (! ips, vps = add(vps, ps); ips = #vps); print1(ips, ", "););} \\ _Michel Marcus_, Nov 15 2015
%o (PARI)
%o 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; };
%o write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)1, " ", vec[n])); }
%o A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ This function from _Charles R Greathouse IV_, Aug 17 2011
%o write_to_bfile(1,rgs_transform(vector(100000,n,A046523(n))),"b101296.txt");
%o \\ Second PARIprogram from _Antti Karttunen_, May 12 2017
%Y Cf. A025487, A046523, A064839 (ordinal transform of this sequence) and arrays A095904, A179216.
%Y Cf. A000005, A008683.
%Y Cf. also A254524, A286603, A286605, A286610, A286619, A286621, A286622, A286626, A286378 for similarly constructed sequences.
%K easy,nonn
%O 1,2
%A _David Wasserman_, Dec 21 2004
%E Data section extended to 120 terms by _Antti Karttunen_, May 12 2017
