# Puzzles/Exp With Sub

Find an expression for the sequence , for any . 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`.

**Spoiler Alert!**

## 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

By Roger Hui

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 * ... `.

-- Oleg Kobchenko DateTime(2006-02-06T07:22:19Z)

Contributed by Oleg Kobchenko