# Puzzles/Exp With Sub

Find an expression for the sequence ${\displaystyle \{x\,k^{i}\}_{i=0\dots N-1}}$, for any ${\displaystyle x\in \mathbf {R} ;\,k,N\in \mathbf {N} }$. E.g.

   7.5*5^i.8   NB. x*k^i.N
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938


using subtraction (dyadic -) as the only numeric operation. That is only structural operations are allowed besides constants (i. or @. are OK, m o. or m b. are not). The expression should not use any constants other than the three x, k and N.

The time/space performance can be better than the original expression x*k^i.N, which is especially visible with large N>1000.

## Solutions

   plus=: - 0&-
times=: 4 :'x. plus ^:y. 0'
sequence=: 4 :0
'k N'=.y.
x.times k times^:(i.N) 1
)
7.5 sequence 5 8
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938


By [|Raul_Miller]]

This solution with N=12 gives out of memory. -- Oleg Kobchenko DateTime(2006-01-26T23:49:39Z)

   plus =: [ - -~@[ - ]
times=: plus /@$~"0 NB. x+i pow =: times/@$~"0  NB. x^i

7.5 times times/\ 1,7$5 7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938 7.5 times 5 pow i.8 7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938  With N=12 on 256 Mb limit this solution gives limit error. -- Oleg Kobchenko DateTime(2006-01-26T23:49:39Z) I forgot the initial solution, which was reversed into this puzzle, and gave better performance than the direct expression. It was very simple and quite non-trivial. Here's some ideas -- worse that the direct expression by slightly less than an order both in time and space. But they both emulate +, whereas in the original - with previous value of the sequence was used in a simpler manner. This one emulates * with +/@$ as in Roger's solution.

   5 (- (-~ -~))/@\$^:(<8) 7.5
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938


Here * is done with the hook (+^: 0:)

   ((- (-~ -~))^:5 -~)^:(<8) 7.5
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938


What is captured and different from other solutions, is that the order of multiplication is

... * 5 * 5 * 7.5 , rather than

7.5 * 5 * 5 * ... .

Contributed by Oleg Kobchenko