title: How to generate a list of palindromes without a check
body: <p>I'm working on a problem where I'm required to manipulate large lists of palindromes up to a certain number of digits. This should work with numbers up 15 digits. The most common method I've seen for this is iterating through each number and <strong>checking</strong> whether each is a palindrome and then adding that to a list. This is my implementation in java and it works fine.</p>
  
  <pre><code>public class Palindrome {
  
  public ArrayList&lt;Long&gt; List = new ArrayList&lt;Long&gt;();
  public double d;
  
  public Palindrome(double digits) {
      this.d = digits;
  
      long dig = (int)(Math.pow(10,digits));
  
      for (long i = 1; i &lt;= dig; i++) {
  
          long a = i;
          long b = inverse(a);
          if (a == b) {
              List.add(a);
          }
      }
  
  public long inverse(long x){
      long inv = 0;
      while (x &gt; 0) {
          inv = inv * 10 + x % 10;
          x = x / 10;
      }
      return inv;
  }
  
  }
  </code></pre>
  
  <p>Only problem is it's pretty slow when I get to 10+ digit palindromes. I've been considering alternative ways to create this list and one consideration I've had is generating the list of palindromes rather than iterating through each number and checking if it's a palindrome.</p>
  
  <p>I'm still working on paper but the pattern isn't as obvious as I thought I would find it to turn into pseudocode. I'm working it out that for n number of digits, going from i to n, if the number of digits is even, generate numbers from 1 up to [10^(i/2 + 1) - 1]. Then append the reverse of each number to itself. A little stuck on how to do it for the odd digits. That's where I am right now.</p>
  
  <p>I will come back with my own response if I figure this out  and implement the code but in the meantime, I would just like to know if anyone has done this before or has an alternative method I've overlooked that would be more efficient.</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>So I did manage to work out something thanks to all your suggestions. I decided to work with the numbers as strings but contrary to what I intended this has actually increased the runtime :/</p>
  
  <pre><code>public class Palindrome2 {
  public ArrayList&lt;Long&gt; List = new ArrayList&lt;Long&gt;();
  public double d;
  
  public Palindrome2(double digits) {
      this.d = digits;
  
      for (long n = 1; n &lt;= d; n++) {
          if (n == 1) {
              for (long i = 1; i &lt; 10; i++) {
                  List.add(i);
              }
          }
  
          if (n % 2 != 0 &amp;&amp; n != 1) {
              long max = (long) Math.pow(10, (n + 1) / 2);
              long min = (long) Math.pow(10, Math.floor(n / 2));
  
              for (long i = min; i &lt; max; i++) {
                  String str = Long.toString(i);
                  str = str + removeFirst(reverse(str));
                  Long x = Long.parseLong(str);
                  List.add(x);
              }
          } else if (n % 2 == 0) {
              long max = (long) (Math.pow(10, Math.floor((n + 1) / 2)) - 1);
              long min = (long) Math.pow(10, (n / 2) - 1);
  
              for (long i = min; i &lt;= max; i++) {
                  String str = Long.toString(i);
                  str = str + reverse(str);
                  Long x = Long.parseLong(str);
                  List.add(x);
              }
          }
      }
  }
  
  public String reverse(String x) {
      String rev = new StringBuffer(x).reverse().toString();
      return rev;
  }
  
  public String removeFirst(String x) {
      return x.substring(1);
  }
  </code></pre>
  
  <p>}</p>
  
  <p>Once again, accurate but still slow :(</p>