cp's OEIS Frontend

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

%I A101296 #72 Aug 30 2024 22:11:23
%S A101296 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 A101296 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 A101296 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 A101296 n has the a(n)-th distinct prime signature.
%C A101296 From _Antti Karttunen_, May 12 2017: (Start)
%C A101296 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:
%C A101296     A000005(i) = A000005(j), A008683(i) = A008683(j), A286605(i) = A286605(j).
%C A101296 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)
%C A101296 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
%H A101296 Michel Marcus (terms 1..10000) & Antti Karttunen, <a href="/A101296/b101296.txt">Table of n, a(n) for n = 1..100000</a>
%F A101296 A025487(a(n)) = A046523(n).
%F A101296 Indices of records give A025487. - _Michel Marcus_, Nov 16 2015
%F A101296 From _David A. Corneth_, May 12 2017: (Start) [Corresponding characteristic function in brackets]
%F A101296 a(A000012(n)) = 1 (sig.: ()).      [A063524]
%F A101296 a(A000040(n)) = 2 (sig.: (1)).     [A010051]
%F A101296 a(A001248(n)) = 3 (sig.: (2)).     [A302048]
%F A101296 a(A006881(n)) = 4 (sig.: (1,1)).   [A280710]
%F A101296 a(A030078(n)) = 5 (sig.: (3)).
%F A101296 a(A054753(n)) = 6 (sig.: (1,2)).   [A353472]
%F A101296 a(A030514(n)) = 7 (sig.: (4)).
%F A101296 a(A065036(n)) = 8 (sig.: (1,3)).
%F A101296 a(A007304(n)) = 9 (sig.: (1,1,1)). [A354926]
%F A101296 a(A050997(n)) = 10 (sig.: (5)).
%F A101296 a(A085986(n)) = 11 (sig.: (2,2)).
%F A101296 a(A178739(n)) = 12 (sig.: (1,4)).
%F A101296 a(A085987(n)) = 13 (sig.: (1,1,2)).
%F A101296 a(A030516(n)) = 14 (sig.: (6)).
%F A101296 a(A143610(n)) = 15 (sig.: (2,3)).
%F A101296 a(A178740(n)) = 16 (sig.: (1,5)).
%F A101296 a(A189975(n)) = 17 (sig.: (1,1,3)).
%F A101296 a(A092759(n)) = 18 (sig.: (7)).
%F A101296 a(A189988(n)) = 19 (sig.: (2,4)).
%F A101296 a(A179643(n)) = 20 (sig.: (1,2,2)).
%F A101296 a(A189987(n)) = 21 (sig.: (1,6)).
%F A101296 a(A046386(n)) = 22 (sig.: (1,1,1,1)).
%F A101296 a(A162142(n)) = 23 (sig.: (2,2,2)).
%F A101296 a(A179644(n)) = 24 (sig.: (1,1,4)).
%F A101296 a(A179645(n)) = 25 (sig.: (8)).
%F A101296 a(A179646(n)) = 26 (sig.: (2,5)).
%F A101296 a(A163569(n)) = 27 (sig.: (1,2,3)).
%F A101296 a(A179664(n)) = 28 (sig.: (1,7)).
%F A101296 a(A189982(n)) = 29 (sig.: (1,1,1,2)).
%F A101296 a(A179666(n)) = 30 (sig.: (3,4)).
%F A101296 a(A179667(n)) = 31 (sig.: (1,1,5)).
%F A101296 a(A179665(n)) = 32 (sig.: (9)).
%F A101296 a(A189990(n)) = 33 (sig.: (2,6)).
%F A101296 a(A179669(n)) = 34 (sig.: (1,2,4)).
%F A101296 a(A179668(n)) = 35 (sig.: (1,8)).
%F A101296 a(A179670(n)) = 36 (sig.: (1,1,1,3)).
%F A101296 a(A179671(n)) = 37 (sig.: (3,5)).
%F A101296 a(A162143(n)) = 38 (sig.: (2,2,2)).
%F A101296 a(A179672(n)) = 39 (sig.: (1,1,6)).
%F A101296 a(A030629(n)) = 40 (sig.: (10)).
%F A101296 a(A179688(n)) = 41 (sig.: (1,3,3)).
%F A101296 a(A179689(n)) = 42 (sig.: (2,7)).
%F A101296 a(A179690(n)) = 43 (sig.: (1,1,2,2)).
%F A101296 a(A189991(n)) = 44 (sig.: (4,4)).
%F A101296 a(A179691(n)) = 45 (sig.: (1,2,5)).
%F A101296 a(A179692(n)) = 46 (sig.: (1,9)).
%F A101296 a(A179693(n)) = 47 (sig.: (1,1,1,4)).
%F A101296 a(A179694(n)) = 48 (sig.: (3,6)).
%F A101296 a(A179695(n)) = 49 (sig.: (2,2,3)).
%F A101296 a(A179696(n)) = 50 (sig.: (1,1,7)).
%F A101296 (End)
%e A101296 From _David A. Corneth_, May 12 2017: (Start)
%e A101296 1 has prime signature (), the first distinct prime signature. Therefore, a(1) = 1.
%e A101296 2 has prime signature (1), the second distinct prime signature after (1). Therefore, a(2) = 2.
%e A101296 3 has prime signature (1), as does 2. Therefore, a(3) = a(2) = 2.
%e A101296 4 has prime signature (2), the third distinct prime signature after () and (1). Therefore, a(4) = 3. (End)
%e A101296 From _Antti Karttunen_, May 12 2017: (Start)
%e A101296 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).
%e A101296 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 A101296 For n = 3, A046523(2) = 2, which was already encountered as A046523(1), thus we set a(3) = a(2) = 2.
%e A101296 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 A101296 For n = 5, A046523(5) = 2, as for the first time encountered at n = 2, thus we set a(5) = a(2) = 2.
%e A101296 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 A101296 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.
%e A101296 For n = 9, A046523(9) = 4, as for the first time encountered at n = 4, thus a(9) = 3.
%e A101296 (End)
%e A101296 From _David A. Corneth_, May 12 2017: (Start)
%e A101296 (Rough) description of an algorithm of computing the sequence:
%e A101296 Suppose we want to compute a(n) for n in [1..20].
%e A101296 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 A101296 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A101296 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 A101296 [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 A101296 [1, 2, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
%e A101296 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:
%e A101296 [1, 2, 2, 3, 2, 0, 2, 0, 3, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
%e A101296 Similarily, after m = 6, we get
%e A101296 [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 A101296 [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 A101296 [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 A101296 [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 A101296 [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)
%e A101296 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
%p A101296 A101296 := proc(n)
%p A101296     local a046523, a;
%p A101296     a046523 := A046523(n) ;
%p A101296     for a from 1 do
%p A101296         if A025487(a) = a046523 then
%p A101296             return a;
%p A101296         elif A025487(a) > a046523 then
%p A101296             return -1 ;
%p A101296         end if;
%p A101296     end do:
%p A101296 end proc: # _R. J. Mathar_, May 26 2017
%t A101296 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 A101296 (PARI) find(ps, vps) = {for (k=1, #vps, if (vps[k] == ps, return(k)););}
%o A101296 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
%o A101296 (PARI)
%o A101296 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 A101296 write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
%o A101296 write_to_bfile(1,rgs_transform(vector(100000,n,A046523(n))),"b101296.txt");
%o A101296 \\ _Antti Karttunen_, May 12 2017
%Y A101296 Cf. A025487, A046523, A064839 (ordinal transform of this sequence), A181819, and arrays A095904, A179216.
%Y A101296 Cf. A000005, A008683.
%Y A101296 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).
%Y A101296 Cf. also A077462, A305897 (stricter variants, with finer partitioning) and A254524, A286603, A286605, A286610, A286619, A286621, A286622, A286626, A286378 for other similarly constructed sequences.
%K A101296 easy,nonn
%O A101296 1,2
%A A101296 _David Wasserman_, Dec 21 2004
%E A101296 Data section extended to 120 terms by _Antti Karttunen_, May 12 2017
%E A101296 Minor edits/corrections by _M. F. Hasler_, Jul 18 2019