Riffs & Rotes & A061396

[David W. Wilson]

Jon Awbrey wrote:
> 
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> 
> David W. Wilson wrote:
> 
> JA: Re:
> 
>     ...
> 
>     Table 3.  Triangle in which k-th row lists natural number
>               values for the collection of riffs with k nodes:
>     --o------------------------------------------------------------------------------
>     k | natural numbers n such that |riff(n)| = k
>     --o------------------------------------------------------------------------------
>     0 |    1;
>     1 |    2;
>     2 |    3,    4;
>     3 |    5,    6,    7,    8,     9,    16;
>     4 |   10,   11,   12,   13,    14,    17,     18,     19,     23,     25,
>       |   27,   32,   49,   53,    64,    81,    128,    256,    512,  65536;
>     5 |   15,   20,   21,   22,    24,    26,     28,     29,     31,     34,
>       |   36,   37,   38,   41,    43,    46,     48,     50,     54,     59,
>       |   61,   67,   83,   97,    98,   103,    106,    121,    125,    131,
>       |  162,  169,  227,  241,   243,   289,    311,    343,    361,    419,
>       |  529,  625,  719,  729,  1024,  1619,   2048,   2187,   2401,   2809,
>       | 3671, 4096, 6561, 8192, 16384, 19683, 131072, 262144, 524288, 821641,
>       | 8388608,  33554432,  43046721,  134217728,  4294967296,  562949953421312,
>       | 9007199254740992,  18446744073709551616,  2417851639229258349412352,
>       | 2^128,  2^256,  2^512,  2^65536;
>       |
>     --o------------------------------------------------------------------------------
> 
> JA: 30 = p^1 p^2 p^3 = p.p< .p<
>                            p   p<
>                                  p
> 
> I meant, of course, to write:
> 
>     30 = p_1 p_2 p_3 = p.p< .p<
>                            p   p<
>                                  p
> 
> JA: => |riff(30)| = 6
> 
>     and 30 is the least number not in the above table,
>     so we have Min Seq = 1, 2, 3, 5, 10, 15, 30, ...
>     which is not in EIS.
> 
>     Unless I have made the classic mistake of staying up too late again.
> 
>     Which I will remedy, post haste.
> 
> DW: I was holding back these sequences, but Jon has forced my hand ...
> 
> Sorry, David, I am new here, and had no clue that
> some brand of poker was being played.  I was just
> treating it like all of my other discussion groups,
> where I am also much too chatty for anybody's good,
> but where nothing much is at stake but time, all too
> precious time.  I think that I indicated in my initial
> note that this is no longer my active arena, and my whole
> reason for being here is turn this old hobby horse of mine
> over to abler cowhands, of whose ability I already have more
> than ample evidence.  So, count the ways, and do as you will!
> As long as I can keep it recreational, I will skulk about the
> old corral, and kibbitz on what all's going on, but I already
> had my fill of this damned ole rodeo in my own wrangler days.
> But I would, for a little while, like to try and comprehend
> what is sprung from these seeds, so if you could explain
> what is meant by a "core sequence", I would like that.
> DW: Here is Jon's sequence extended somewhat.
>     I am still looking to compute this more quickly.
> 
> DW:
> | %I A000001
> | %S A000001 1,2,3,5,10,15,30,55,105,165,330,660,1155,2145,4290,7755,15015,30030,
> | %T A000001 54285,100815,201630,403260,705705
> | %N A000001 Smallest k with n nodes in its riff (rooted index-functional forest)
> |            for n.
> | %K A000001 nonn
> | %O A000001 0,2
> | %C A000001 Smallest k with A000000(k) = n.
> | %A A000001 Jon Awbrey (jawbrey at oakland.edu), dww

Let R(n) be the number nodes in the riff of n.  Then we have

    R(n) = R(PROD(p_i^e_i)) = SUM(R(p_i^e_i)) = SUM(R(i) + R(e_i) + 1).

Now suppose we wish to find the smallest n with R(n) = k.  Then we have

    k = SUM(R(p_i^e_i))

that is, the R(p_i^e_i) form a partition of k.  Thus, to find n, we must
run through the partitions {a_j} of k, choose all possible distinct i
and e_i with R(p_i^e_i) = a_j, and minimize n = PROD(p_i^e_i) over these
i and e_i.

In general, there are a large number of prime powers p_i^e_i with
R(p_i^e_i) = a_j.  However, given that our aim is to minimize n, we
can neglect all but the smallest few p_i^e_i for each a_j.  Doing
this makes the computation of n tractable, and allows us to extend the
above sequence to:

1 2 3 5 10 15 30 55 105 165 330 660 1155 2145 4290 7755 15015 30030
54285 100815 201630 403260 705705 1411410 2822820 5645640 11392095
20465445 40930890 79744665 159489330 318978660 637957320 1321483020