login
Row length of A276380(n).
3

%I #19 Sep 15 2022 02:18:03

%S 1,1,1,1,2,1,2,1,1,2,2,1,2,2,2,1,2,1,2,2,2,2,3,1,2,2,1,2,2,2,2,1,2,2,

%T 2,1,2,2,2,2,3,2,3,2,2,3,3,1,2,2,2,2,3,1,2,2,2,2,3,2,3,2,2,1,2,2,2,2,

%U 3,2,3,1,2,2,2,2,3,2,3,2,1,2,2,2,2,3,2,3,2,2,3,3,2,3,3,1,2,2,2,2

%N Row length of A276380(n).

%C a(n) represents the partition size generated by greedy algorithm at A276380(n) such that all parts k are unique and in A003586.

%C See A276380 for further comments about the greedy algorithm.

%C Row n = 1 for n that are in A003586.

%C A237442(n) represents the smallest possible partition size such that all k are distinct and in A003586. The reference defines the "canonic" representation of n in the "dual-base number system", i.e., base(2,3), essentially as those which have length A237442(n).

%C a(n) differs from A237442(n) at n = 41, 43, 59, 86, 88, 91, 113, 118, 123, 135, 155, 172, 176, 177, 182, 185, 209, 215, 226, 236, 239, 248, ... (i.e., A277071).

%D V. Dimitrov, G. Jullien, and R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

%H Michael De Vlieger, <a href="/A277070/b277070.txt">Table of n, a(n) for n = 1..10000</a>

%e a(n) Terms k in row n of A276380:

%e 1 1

%e 1 2

%e 1 3

%e 1 4

%e 2 1,4

%e 1 6

%e 2 1,6

%e 1 8

%e 1 9

%e 2 1,9

%e 2 2,9

%e 1 12

%e 2 1,12

%e 2 2,12

%e 2 3,12

%e 1 16

%e 2 1,16

%e 1 18

%e 2 1,18

%e 2 2,18

%e 2 3,18

%e 2 4,18

%e 3 1,4,18

%e ...

%e a(41) = 3 since A276380(41) = {1,4,36}, but {9,32} is the shortest possible partition of 41 such that all terms are distinct and in A003586.

%e a(88) = 3 since A276380(88) = {1,6,81}, but {16,72} and {24,64} are shorter and have A237442(88) = 2 terms.

%t Table[Length@ DeleteCases[Append[Abs@ Differences@ #, Last@ #], k_ /; k == 0] &@ NestWhileList[# - SelectFirst[# - Range[0, # - 1], Block[{m = #, n = 6}, While[And[m != 1, ! CoprimeQ[m, n]], n = GCD[m, n]; m = m/n]; m == 1] &] &, n, # > 1 &], {n, 100}]

%o (Python)

%o from itertools import count, takewhile

%o N = 100

%o def B(p): return list(takewhile(lambda x: x<=N, (p**i for i in count(0))))

%o B23set = set(b*t for b in B(2) for t in B(3) if b*t <= N)

%o B23lst = sorted(B23set, reverse=True)

%o def a(n):

%o if n in B23set: return 1

%o big = next(t for t in B23lst if t <= n)

%o return a(n - big) + 1

%o print([a(n) for n in range(1, N+1)]) # _Michael S. Branicky_, Sep 14 2022

%Y Cf. A003586, A237442, A276380, A277071.

%K nonn

%O 1,5

%A _Michael De Vlieger_, Sep 27 2016