A297174 -id:A297174 - cp's OEIS frontend

A300250 Restricted growth sequence transform of A297174: a filter sequence recording the prime signatures of divisors of n, with divisors ordered by their magnitude.

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

Offset: 1

Antti Karttunen, Mar 07 2018

nonn

This sequence gives a coarser partitioning of natural numbers than A290110, and finer than A101296:
For all i, j:
  A290110(i) = A290110(j) => a(i) = a(j) => A101296(i) = A101296(j).

			Divisors of 462 are 1, 2, 3, 6, 7, 11, 14, 21, 22, 33, 42, 66, 77, 154, 231, 462.
Divisors of 858 are 1, 2, 3, 6, 11, 13, 22, 26, 33, 39, 66, 78, 143, 286, 429, 858.
If one takes the smallest prime-signature representative (A046523) of each these, one gets in both cases [1, 2, 2, 6, 2, 2, 6, 6, 6, 6, 30, 30, 6, 30, 30, 210]. E.g. 462 = 2*3*7*11 and 858 = 2*3*11*13, which both have the same prime signature as 210 = 2*3*5*7. And similarly for all the other divisors, from which follows that a(462) = a(858).
On the other hand, for 12 = 2*2*3 the divisors are 1, 2, 3, 2*2, 2*3, 2*2*3, and for 18 = 2*3*3 the divisors are 1, 2, 3, 2*3, 3*3, 2*3*3, and because the prime signatures differ both in the fourth and in the fifth places, a(18) != a(12).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A046523, A101296, A297174, A300716.

Differs from similar A290110 for the first time at n=858.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,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])); }
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
v101296 = rgs_transform(vector(up_to, n, A046523(n)));
A101296(n) = v101296[n];
A297174(n) = { my(s=0,i=-1); fordiv(n, d, if(d>1, i += (A101296(d)-1); s += 2^i)); (s); };
write_to_bfile(1,rgs_transform(vector(up_to,n,A297174(n))),"b300250.txt");

A290110 a(n) = the discovery rank of the factorization pattern of the sequence of divisors of n.

Original entry on oeis.org

Offset: 1

Luc Rousseau, Jul 19 2017

nonn

The definition for the factorization pattern of the sequence of divisors of a number n is the same as in sequence A191743. Let's use the abbreviation FPSD. One can generate a list of distinct FPSD by trying all integers, 1, 2, 3, ..., and ignoring duplicates. a(n) is the index of the FPSD of n in this list.
From Antti Karttunen, Mar 07 & 08 2018: (Start)
This is NOT restricted growth sequence transform of A297174, but instead A300250 is, from which this differs for the first time at n=858, where a(858) = 115, while A300250(858) = 75.
This gives a finer partitioning of natural numbers than A300250, and indeed we have:
For all i, j:
  a(i) = a(j) => A300250(i) = A300250(j) => A101296(i) = A101296(j).
(End)

			The divisors of 17 are {1, 17}. They follow the pattern {1, p} which is pattern number 2 in discovery order. a(17)=2.
The divisors of 28 are {1, 2, 4, 7, 14, 28}. They follow the pattern {1, p, p^2, q, p*q, p^2*q}, which is pattern number 9 in discovery order. a(28)=9.
From _Michael De Vlieger_ and _Antti Karttunen_, Mar 07 & 08 2018: (Start)
Divisors of 462 = 2*3*7*11 (p=2, q=3, r=7, s=11) are 1, 2, 3, 6, 7, 11, 14, 21, 22, 33, 42, 66, 77, 154, 231, 462, thus the factorization patterns in the order of increasing divisors are: 1, p, q, pq, r, s, pr, qr, ps, qs, pqr, pqs, rs, prs, qrs and pqrs.
Divisors of 546 = 2*3*7*13 (p=2, q=3, r=7, s=13) are 1, 2, 3, 6, 7, 13, 14, 21, 26, 39, 42, 78, 91, 182, 273, 546, thus the factorization patterns are 1, p, q, pq, r, s, pr, qr, ps, qs, pqr, pqs, rs, prs, qrs and pqrs, that is, identical with those of 462, thus a(546) = a(462).
Divisors of 858 = 2*3*11*13 (p=2, q=3, r=11, s=13) are 1, 2, 3, 6, 11, 13, 22, 26, 33, 39, 66, 78, 143, 286, 429, 858, thus the factorization patterns are 1, p, q, pq, r, s, pr, ps, qr, qs, pqr, pqs, rs, prs, qrs and pqrs. At the 8th divisor (26), we see that pattern ps is different from pattern qr of the 8th divisor of 546 (21), thus a(858) is not equal to a(546).
(End)

Michael De Vlieger, Table of n, a(n) for n = 1..65537

Cf. A191743, A300250.

FactorizationPattern[n_] := Module[
  {pn, fd, f1, f2, d},
  pn = First /@ FactorInteger[n];
  fd = FactorInteger[ReplacePart[Divisors[n], 1 -> {}]];
  f1 = (ReplacePart[#,
      1 -> FromCharacterCode[
        111 + First[Position[pn, First[#]]]]]) &;
  f2 = (f1 /@ #) &;
  fd = f2 /@ fd;
  f1 = (Power[First[#], Last[#]]) &;
  For[i = 1, i <= Length[fd], i++,
   d = fd[[i]];
   For[j = 1, j <= Length[d], j++,d[[j]] = f1[d[[j]]];];
   d = Product[x, {x, d}];
   fd[[i]] = d;
  ];
  fd
]
ListFactorizationPatternIndices[n_] := Module[
  {mem, k, i, p, a},
  mem = Association[];
  a = {}; k = 0;
  For[i = 1, i \[LessSlantEqual] n, i++,
   p = FactorizationPattern[i];
   If[KeyExistsQ[mem, p],,
    k++;
    mem = Append[mem, p -> k]
   ];
   a = Append[a, mem[p]]
  ];
  a
]
ListFactorizationPatternIndices[80]
(* or *)
f[n_] := If[n==1, 1, Block[{p = First /@ FactorInteger@n, z,x}, z= Table[p[[i]] -> x[i], {i, Length@p}]; Times @@ (((#[[1]] /. z)^#[[2]]) & /@ FactorInteger@ #) & /@ Divisors[n]]]; A = <||>; Table[k = f[n]; If[ KeyExistsQ[A, k], A[k], t = 1 + Length@A; A[k] = t], {n, 80}] (* Giovanni Resta, Jul 20 2017 *)

A191743(n) = MIN(k such that a(k)=n).
a(p) = 2, for p prime;
a(p^2) = 3, for p prime;
a(p*q) = 4, for p, q distinct primes.

More terms from Michael De Vlieger and Antti Karttunen, Mar 07 2018

A300716 a(1) = 0; for n > 1, a(n) = Product_{d|n, 1A101296(d)-1).

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 6, 2, 4, 1, 60, 1, 4, 4, 42, 1, 60, 1, 60, 4, 4, 1, 4620, 2, 4, 6, 60, 1, 1000, 1, 546, 4, 4, 4, 21780, 1, 4, 4, 4620, 1, 1000, 1, 60, 60, 4, 1, 1021020, 2, 60, 4, 60, 1, 4620, 4, 4620, 4, 4, 1, 6897000, 1, 4, 60, 12558, 4, 1000, 1, 60, 4, 1000, 1, 75162780, 1, 4, 60, 60, 4, 1000, 1, 1021020, 42, 4, 1

Offset: 1

Antti Karttunen, Mar 13 2018

nonn

a(n) = Product formed from the primes indexed with the prime signatures of proper divisors of n.
The restricted growth sequence transform of this sequence is A101296 because from the set of prime signatures of the proper divisors of n it is always possible to determine the prime signature of n itself, and vice versa, from the prime signature of n, we can form the set of prime signatures of all its proper divisors.
For all i, j: a(i) = a(j) <=> A101296(i) = A101296(j).

			For n = 12, whose proper divisors > 1 are 2, 3, 4, 6, their prime signature ranks from A101296 are: 2, 2, 3, 4. We subtract one from each, to form product prime(1)*prime(1)*prime(2)*prime(3) = 2*2*3*5 = 60, which is thus value of a(12).

Antti Karttunen, Table of n, a(n) for n = 1..8192
Index entries for sequences computed from exponents in factorization of n

Cf. A046523, A101296, A297174, A300250.

Cf. also A292258, A294897, A300827.

Block[{nn = 83, s}, s = 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}]; Table[If[n == 1, 0, Times @@ Map[Prime[FirstPosition[Keys@ s, #][[1]] - 1] &, Most@ Rest@ Divisors@ n]], {n, nn}]] (* Michael De Vlieger, Mar 13 2018 *)

up_to = 8192;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,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])); }
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
v101296 = rgs_transform(vector(up_to, n, A046523(n)));
A101296(n) = v101296[n];
A300716(n) = { my(m=1); if(1==n, 0, fordiv(n,d,if((d>1)&(dA101296(d)-1))); (m)); };
for(n=1,up_to,write("b300716.txt", n, " ", A300716(n)));

cp's OEIS Frontend

A300250 Restricted growth sequence transform of A297174: a filter sequence recording the prime signatures of divisors of n, with divisors ordered by their magnitude.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A290110 a(n) = the discovery rank of the factorization pattern of the sequence of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A300716 a(1) = 0; for n > 1, a(n) = Product_{d|n, 1A101296(d)-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI