

A307544


Irregular triangle read by rows: T(n,k) = A087207(A307540(n,k)).


1



0, 1, 3, 2, 7, 5, 6, 4, 15, 11, 13, 9, 14, 10, 12, 8, 31, 23, 27, 19, 29, 21, 25, 30, 17, 22, 26, 18, 28, 20, 24, 16, 63, 47, 55, 59, 39, 43, 51, 61, 35, 45, 53, 57, 37, 62, 41, 49, 46, 54, 33, 58, 38, 42, 50, 60, 34, 44, 52, 56, 36, 40, 48, 32, 127, 95, 111, 119
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Row n contains m in A005117 such that A006530(m) = n, sorted such that phi(m)/m increases as k increases.
Let m be the squarefree kernel A007947(m') of m'. We only consider squarefree m since phi(m)/m = phi(m')/m'. Let prime p  n and prime q be a nondivisor of n.
Since m is squarefree, we might encode the multiplicities of its prime divisors in a positional notation M that is finite at n significant digits. For example, m = 42 can be encoded reverse(A067255(42)) = 1,0,1,1 = 7^1 * 5^0 * 3^1 * 2^1. It is necessary to reverse row m of A067255 (hereinafter simply A067255(m)) so as to preserve zeros in M = A067255(m) pertaining to small nondivisor primes q < p. The code M is a series of 0's and 1's since m is squarefree. Then it is clear that row n contains all m such that A067255(m) has n terms, and there are 2^(n  1) possible terms for n >= 1.
We may use an approach that generates the binary expansion of the range 2^(n  1) < M < 2^n  1, or we may append 1 to the reversed (n  1)tuples of {1, 0} (as A059894) to achieve codes M > m for each row n.
Originally it was thought that the codes M were in order of the latter algorithm, and we could avoid sorting. Observation shows that the m still require sorting by the function phi(m)/m indeed to be in increasing order in row n. Still, the latter approach is slightly more efficient than the former in generating the sequence.
This sequence interprets the code M as a binary value. The sequence is a permutation of the natural numbers since the ratio phi(m)/m is unique for squarefree m.
This sequence and A059894 are identical for 1 <= n <= 23.
Numbers of terms in rows n of this sequence and A059894 (partitioned by powers of 2) that are coincident: 1, 2, 4, 8, 14, 14, 10, 26, 14, 20, 10, 16, 22, 12, 18, 18, 16, 14, 18, 18, 18, 14, 16, ...}.
The graphs of this sequence and A059894 are similar.
The graph of this sequence feature squares of size 2^(j1) at (x,y) = (h,h) where h = 2^j, integers, that have piradian rotational symmetry.


LINKS



FORMULA

For n > 0, row lengths = 2^(n  1).
T(n,2^(n  1)) = 2^(n  1).


EXAMPLE

First terms of this sequence appear bottom to top in the chart below. The values of n appear in the header, values m = T(n,k) followed parenthetically by phi(m)/m appear in column n. In square brackets, we write the multiplicities of primes in positional order with the smallest prime at right (bigendian). The x axis plots k according to primepi(gpf(m)), while the y axis plots k according to phi(m)/m:
0 1 2 3 4
. . . . .
 1 
(1/1) . . . .
[0] . . . .
. . . . .
. . . . 7
. . . 5 (6/7)
. . . (4/5) [1000]
. . . [100] .
. . . . 35
. . 3 . (24/35)
. . (2/3) . [1100]
. . [10] . .
. . . . .
. . . . 21
. . . . (4/7)
. . . 15 [1010]
. . . (8/15) .
. 2 . [110] .
. (1/2) . . .
. [1] . . 105
. . . . (16/35)
. . . . [1110]
. . . . 14
. . . 10 (3/7)
. . . (2/5) [1001]
. . . [101] .
. . . . 70
. . 6 . (12/35)
. . (1/3) . [1101]
. . [11] . 42
. . . 30 (2/7)
. . . (4/15) [1011]
. . . [111] 210
. . . . (8/35)
. . . . [1111]
...
a(1) = 0 since T(0,1) = 1 = empty product.
a(2) = 1 since T(1,1) = 2 = 2^1 > binary "1" = decimal 1.
a(3) = 3 since T(2,1) = 6 = 2^1 * 3^1 > binary "11" = decimal 3.
a(4) = 2 since T(2,2) = 3 = 2^0 * 3^1 > binary "10" = decimal 2.
a(5) = 7 since T(3,1) = 30 = 2^1 * 3^1 * 5^1 > binary "111" = decimal 7, etc.
Graph of first 32 terms: (Begin)
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
(End)
Arranged as a binary tree:
0

...................1...................
3 2
7......../ \........5 6......../ \........4
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
15 11 13 9 14 10 12 8
31 23 27 19 29 21 25 30 17 22 26 18 28 20 24 16
etc.
(End)


MATHEMATICA

Prepend[Array[SortBy[#, Last] &@ Map[{#2, EulerPhi[#1]/#1} & @@ {Times @@ MapIndexed[Prime[First@ #2]^#1 &, Reverse@ #], FromDigits[#, 2]} &, Map[Prepend[Reverse@ #, 1] &, Tuples[{1, 0}, #  1]]] &, 7], {{0, 0, 1}}][[All, All, 1]] // Flatten


PROG

(PARI)
up_to = 1023;
rat(n) = { my(m=1, p=2); while(n, if(n%2, m *= (p1)/p); n >>= 1; p = nextprime(1+p)); (m); };
cmpA307544(a, b) = if(!a, sign(b), if(!b, sign(a), my(as=logint(a, 2), bs=logint(b, 2)); if(as!=bs, sign(asbs), sign(rat(a)rat(b)))));
A307544list(up_to) = vecsort(vector(1+up_to, n, n1), cmpA307544);
v307544 = A307544list(up_to);


CROSSREFS

Cf. A000010, A000040, A000079, A000225, A002110, A005117, A006094, A006530, A007947, A048672, A059894, A067255, A087207, A225679, A225680, A306237, A307540.


KEYWORD



AUTHOR



STATUS

approved



