# Dina's Paintings

Dina loves most numbers. In fact, she loves every number that is not a multiple of n (she really hates the number n). For her friends’ birthdays this year, Dina has decided to draw each of them a sequence of n−1 flowers. Each of the flowers will contain between 1 and n−1 flower petals (inclusive). Because of her hatred of multiples of n, the total number of petals in any non-empty contiguous subsequence of flowers cannot be a multiple of n. For example, if n=5, then the top two paintings are valid, while the bottom painting is not valid since the second, third and fourth flowers have a total of 10 petals. (The top two images are Sample Input 3 and 4.)

Dina wants her paintings to be unique, so no two paintings will have the same sequence of flowers. To keep track of this, Dina recorded each painting as a sequence of n−1 numbers specifying the number of petals in each flower from left to right. She has written down all valid sequences of length n−1 in lexicographical order. A sequence a1,a2,…,a(n−1) is lexicographically smaller than b1,b2,…,bn−1 if there exists an index k such that ai=bi for i < k and ak < bk.

What is the kth sequence on Dina’s list?

Input The input consists of a single line containing two integers n (2≤n≤1000), which is Dina’s hated number, and k (1≤k≤1018), which is the index of the valid sequence in question if all valid sequences were ordered lexicographically. It is guaranteed that there exist at least k valid sequences for this value of n.

Output Display the kth sequence on Dina’s list.

Sample Input 1
4 3
Sample Output 1
2 1 2


Sample Input 2
2 1
Sample Output 2
1


Sample Input 3
5 22
Sample Output 3
4 3 4 2


Sample Input 4
5 16
Sample Output 4
3 3 3 3

• Welcome to PPCG. Nice first question. – ElPedro Nov 10 '18 at 12:21
• Did you write this question or is it from another source? – Peter Taylor Nov 10 '18 at 17:23

n#k=[d|d<-mapM id$[1..n]<$[2..n],all(\x->mod x n>0)$p d]!!k p(x:y)=scanl(+)x<>p$y
p x=x


Uses 0-based indexing. Needs the latest version of Prelude which is not installed on TIO, hence an additional import.

Try it online!

   d|d<-mapM id$[1..n]<$[2..n]    -- keep all 'd' from the lists of numbers [1..n] of
-- length n-1
, all(\x->      )            -- where all elements 'x' from
p d        -- the sums of the subsequences of 'd'
mod x n>0          -- are not a multiple of n
[                           ]!!k -- pick the 'k'th element

p(x:y)=scanl(+)x<>p$y -- the sums of subsequences are calculated by -- prepending the cumulative sums of the list to -- a recursive call with the tail of the list p x=x -- base case for recursion: empty list  # Jelly, 12 bytes ’ṗẆ§%ẠʋƇ⁸ị@  A dyadic Link accepting n on the left and k on the right. Try it online! (no way this will work for large n, but would in theory) ### How? ’ṗẆ§%ẠʋƇ⁸ị@ - Link: integer n, integer k ’ - decrement n -> n-1  - use for both arguments of: ṗ - Cartesian power (all (n-1)^2 flower sequences - lex order) ⁸ - chain's left argument, n (as right argument for...) Ƈ - filter keep those (sequences) which are truthy under: ʋ - last four links as a dyad (f(sequence, n)): Ẇ - all ((n-1)n/2) contiguous sublists (of the sequence) § - sum each % - modulo (n) Ạ - all? (all non-zero?) @ - with swapped arguments (i.e. f(k, listOfValidSequences) ị - index into (1-based)  # Perl 6, 74 68 bytes {([X] (1..^$^a)xx$a-1).grep(!*[^*X.. ^*].grep:{$_&.sum%%$a})[$^b-1]}


Try it online!

Anonymous code block that returns a list of numbers, or an integer in the case of $$\n=2\$$.

### Explanation:

{([X] (1..^$^a)xx$a-1).grep(!*[^*X.. ^*].grep:{$_&.sum%%$a})[$^b-1]} { } # Anonymous code block ([X] (1..^$^a)xx$a-1) # From all n length sequences of 1 to n-1 .grep( ) # Filter by ! .grep:{ } # None of *[^*X.. ^*] # All partitions (including empty lists)$_    # Are non-empty
&.sum%%$a # And the sum is divisible by n [$^b-1]  # Get the kth index of the list


# Charcoal, 35 bytes

ＮθＩ↨§Φ…Ｘθ⁻θ²Ｘθ⊖θ¬ΦθΦλ¬﹪Σ✂↨ιθνλ¹θ⊖ηθ


Try it online! Link is to verbose version of code. Works by taking the range $$\ n^{n-2} \ldots n^{n-1}-1 \$$ in base $$\ n \$$ and filtering out illegal sequences (including ones with zero digits). Explanation:

Ｎ                                   Input n as a number
θ                                  Save in variable
θ                           n
Ｘ                            To the power
θ                         n
⁻                          Minus
²                        2
…                             Ranged up to
θ                      n
Ｘ                       To the power
θ                    n
⊖                     Decremented
Φ                              Filtered i by
¬                   Not
θ                 Implicit range 0 .. n-1
Φ                  Filtered l by
λ               Implicit range 0 .. l
Φ                Filtered m by
¬              Not
Σ            Sum
ι         i
↨          Converted to base
θ        q
✂           Sliced
ν       From m
λ      To l
¹     Step 1
﹪             Modulo
θ    n
§                               Indexed by
η  Second input k
⊖   Decremented
↨                                Converted to base
θ n
Ｉ                                 Cast to string
Implicitly printed
`