title: Expressing an integer as a series of multipliers
body: <p><strong><em>Scroll down to see latest edit, I left all this text here just so that I don't invalidate the replies this question has received so far!</em></strong></p>
  
  <hr>
  
  <p>I have the following brain teaser I'd like to get a solution for, I have tried to solve this but since I'm not mathematically that much above average (<em>that is, I think I'm very close to average</em>) I can't seem wrap my head around this.</p>
  
  <p>The problem: Given number <code>x</code> should be split to a serie of <code>multipliers</code>, where each <code>multiplier &lt;= y</code>, <code>y</code> being a constant like 10 or 16 or whatever. In the serie (technically an <code>array of integers</code>) the last number should be added instead of multiplied to be able to convert the multipliers back to original number.</p>
  
  <p>As an example, lets assume <code>x=29</code> and <code>y=10</code>. In this case the expected array would be <code>{10,2,9}</code> meaning <code>10*2+9</code>. However if <code>y=5</code>, it'd be <code>{5,5,4}</code> meaning <code>5*5+4</code> or if <code>y=3</code>, it'd be <code>{3,3,3,2}</code> which would then be <code>3*3*3+2</code>.</p>
  
  <p>I tried to solve this by doing something like this:</p>
  
  <ol>
  <li>while <code>x &gt;= y</code>, store <code>y</code> to <code>multipliers</code>, then <code>x = x - y</code></li>
  <li>when <code>x &lt; y</code>, store <code>x</code> to <code>multipliers</code></li>
  </ol>
  
  <p>Obviously this didn't work, I also tried to store the "leftover" part separately and add that after everything else but that didn't work either. I believe my main problem is that I try to think this in a way too complex manner while the solution is blatantly obvious and simple.</p>
  
  <p>To reiterate, these are the limits this algorithm should have:</p>
  
  <ul>
  <li>has to work with 64bit longs</li>
  <li>has to return an array of 32bit integers (...well, shorts are OK too)</li>
  <li>while support for signed numbers (both + and -) would be nice, if it helps the task only unsigned numbers is a must</li>
  </ul>
  
  <p>And while I'm doing this using Java, I'd rather take any possible code examples as pseudocode, I specifically do NOT want readily made answers, I just need a nudge (well, more of a strong kick) so that I can solve this at least partly myself. Thanks in advance.</p>
  
  <h2>Edit: Further clarification</h2>
  
  <p>To avoid some confusion, I think I should reword this a bit:</p>
  
  <ul>
  <li>Every integer in the result array should be less or equal to y, including the last number.</li>
  <li>Yes, the last number is just a magic number.</li>
  <li>No, this is isn't modulus since then the second number would be larger than y in most cases.</li>
  <li>Yes, there is multiple answers to most of the numbers available, however I'm looking for the one with least amount of math ops. As far as my logic goes, that means finding the maximum amount of as big multipliers as possible, for example <code>x=1 000 000,y=100</code> is <code>100*100*100</code> even though <code>10*10*10*10*10*10</code> is equally correct answer math-wise.</li>
  </ul>
  
  <p>I need to go through the given answers so far with some thought but if you have anything to add, please do! I do appreciate the interest you've already shown on this, thank you all for that.</p>
  
  <h2>Edit 2: More explanations + bounty</h2>
  
  <p>Okay, seems like what I was aiming for in here just can't be done the way I thought it could be. I was too ambiguous with my goal and after giving it a bit of a thought I decided to just tell you in its entirety what I'd want to do and see what you can come up with.</p>
  
  <p>My goal originally was to come up with a specific method to pack 1..n large integers (aka longs) together so that their String representation is notably shorter than writing the actual number. Think multiples of ten, 10^6 and 1 000 000 are the same, however the representation's length in characters isn't.</p>
  
  <p>For this I wanted to somehow combine the numbers since it is expected that the numbers are somewhat close to each other. I firsth thought that representing <code>100, 121, 282</code> as <code>100+21+161</code> could be the way to go but the saving in string length is neglible at best and really doesn't work that well if the numbers aren't very close to each other. Basically I wanted more than ~10%.</p>
  
  <p>So I came up with the idea that what if I'd group the numbers by common property such as a multiplier and divide the rest of the number to individual components which I can then represent as a string. This is where this problem steps in, I thought that for example 1 000 000 and 100 000 can be expressed as 10^(5|6) but due to the context of my aimed usage this was a bit too flaky:</p>
  
  <p><strong>The context is Web.</strong> RESTful URL:s to be specific. That's why I mentioned of thinking of using 64 characters (web-safe alphanumberic non-reserved characters and then some) since  then I could create seemingly random URLs which could be unpacked to a list of integers expressing a set of id numbers. At this point I thought of creating a base 64-like number system for expressing base 10/2 numbers but since I'm not a math genius I have no idea beyond this point how to do it.</p>
  
  <h2>The bounty</h2>
  
  <p>Now that I have written the whole story (sorry that it's a long one), I'm opening a bounty to this question. Everything regarding requirements for the preferred algorithm specified earlier is still valid. I also want to say that I'm already grateful for all the answers I've received so far, I enjoy being proven wrong if it's done in such a manner as you people have done.</p>
  
  <h2>The conclusion</h2>
  
  <p>Well, bounty is now given. I spread a few comments to responses mostly for future reference and myself, you can also check out my <a href="http://stackoverflow.uservoice.com/pages/1722-general/suggestions/178706-add-a-way-to-spread-bounty-to-multiple-answers" rel="nofollow noreferrer">SO Uservoice</a> suggestion about spreading bounty which is related to this question if you think we should be able to spread it among multiple answers.</p>
  
  <hr>
  
  <p><strong>Thank you all for taking time and answering!</strong></p>