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

%I #37 Apr 07 2020 23:23:45

%S 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,

%T 26,18,28,20,24,16,63,47,55,59,39,43,51,61,35,45,53,57,37,62,41,49,46,

%U 54,33,58,38,42,50,60,34,44,52,56,36,40,48,32,127,95,111,119

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

%C Let gpf(m) = A006530(m) and let phi(m) = A000010(m) for m in A005117.

%C Row n contains m in A005117 such that A006530(m) = n, sorted such that phi(m)/m increases as k increases.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C This sequence and A059894 are identical for 1 <= n <= 23.

%C 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, ...}.

%C The graphs of this sequence and A059894 are similar.

%C The graph of this sequence feature squares of size 2^(j-1) at (x,y) = (h,h) where h = 2^j, integers, that have pi-radian rotational symmetry.

%H Antti Karttunen, <a href="/A307544/b307544.txt">Table of n, a(n) for n = 0..16383</a>

%H Michael De Vlieger, <a href="/A307544/a307544.png">Plot comparing A059894 and A307544</a>.

%H Antti Karttunen, <a href="/A307544/a307544.txt">Data supplement: n, a(n) computed for n = 0..65535</a> (including terms 0..16384 previously computed by Michael De Vlieger)

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F For n > 0, row lengths = 2^(n - 1).

%F T(n,1) = 2^n - 1 = A000225(n).

%F T(n,2^(n - 1)) = 2^(n - 1).

%e 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 (big-endian). The x axis plots k according to primepi(gpf(m)), while the y axis plots k according to phi(m)/m:

%e 0 1 2 3 4

%e . . . . .

%e --- 1 ------------------------------------------------

%e (1/1) . . . .

%e [0] . . . .

%e . . . . .

%e . . . . 7

%e . . . 5 (6/7)

%e . . . (4/5) [1000]

%e . . . [100] .

%e . . . . 35

%e . . 3 . (24/35)

%e . . (2/3) . [1100]

%e . . [10] . .

%e . . . . .

%e . . . . 21

%e . . . . (4/7)

%e . . . 15 [1010]

%e . . . (8/15) .

%e . 2 . [110] .

%e . (1/2) . . .

%e . [1] . . 105

%e . . . . (16/35)

%e . . . . [1110]

%e . . . . 14

%e . . . 10 (3/7)

%e . . . (2/5) [1001]

%e . . . [101] .

%e . . . . 70

%e . . 6 . (12/35)

%e . . (1/3) . [1101]

%e . . [11] . 42

%e . . . 30 (2/7)

%e . . . (4/15) [1011]

%e . . . [111] 210

%e . . . . (8/35)

%e . . . . [1111]

%e ...

%e a(1) = 0 since T(0,1) = 1 = empty product.

%e a(2) = 1 since T(1,1) = 2 = 2^1 -> binary "1" = decimal 1.

%e a(3) = 3 since T(2,1) = 6 = 2^1 * 3^1 -> binary "11" = decimal 3.

%e a(4) = 2 since T(2,2) = 3 = 2^0 * 3^1 -> binary "10" = decimal 2.

%e a(5) = 7 since T(3,1) = 30 = 2^1 * 3^1 * 5^1 -> binary "111" = decimal 7, etc.

%e Graph of first 32 terms: (Begin)

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e x

%e (End)

%e From _Antti Karttunen_, Jan 10 2020: (Start)

%e Arranged as a binary tree:

%e 0

%e |

%e ...................1...................

%e 3 2

%e 7......../ \........5 6......../ \........4

%e / \ / \ / \ / \

%e / \ / \ / \ / \

%e / \ / \ / \ / \

%e 15 11 13 9 14 10 12 8

%e 31 23 27 19 29 21 25 30 17 22 26 18 28 20 24 16

%e etc.

%e (End)

%t 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

%o (PARI)

%o up_to = 1023;

%o rat(n) = { my(m=1, p=2); while(n, if(n%2, m *= (p-1)/p); n >>= 1; p = nextprime(1+p)); (m); };

%o cmpA307544(a,b) = if(!a,sign(-b),if(!b,sign(a), my(as=logint(a,2), bs=logint(b,2)); if(as!=bs, sign(as-bs), sign(rat(a)-rat(b)))));

%o A307544list(up_to) = vecsort(vector(1+up_to,n,n-1), cmpA307544);

%o v307544 = A307544list(up_to);

%o A307544(n) = v307544[1+n]; \\ _Antti Karttunen_, Jan 10 2020

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

%K nonn,easy,look,tabf

%O 0,3

%A _Michael De Vlieger_, Apr 19 2019