Timeline for Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2020 at 10:03 | vote | accept | Florian Bauer | ||
| Dec 28, 2020 at 20:50 | comment | added | gnasher729 | Your algorithm ends up doing a prime factorisation of n, and for primes p calculates 1 + GetExpression(p-1). I did additionally an exhaustive search trying GetExpression(d) + GetExpression(n-d). Doing this for small d might be good enough. | |
| Dec 28, 2020 at 12:14 | comment | added | Florian Bauer | Thanks for the info. Since you have found so many counter examples, do you have an idea how i could fix my algorithm? Looking at the example n=46 i see that GetExpression(45)+1 has less 1's than GetExpression(46). So i was thinking of a dynamic programming algorithm where i calculate GetExpression(n) by looking wether GetExpression(n-1)+1 or an multiplication of two numbers has the least amount of 1's. | |
| Dec 27, 2020 at 18:52 | history | edited | gnasher729 | CC BY-SA 4.0 |
added 195 characters in body
|
| Dec 27, 2020 at 18:36 | history | answered | gnasher729 | CC BY-SA 4.0 |