#include <iostream>
#include <conio.h>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm>
using namespace std;
string cand = "";
string max_cand = "";
int inc_pos = 0;
int first_pos = 0;
int sum = 101;
int test_sum = 0;
int counter = 1;
int e_pos = 0;
fstream out1;
int inc(int pos)
    {
    cand[pos]++;
    cand[pos+1]--;
    }
int generate()
    {
    int a = sum/9;
    int b = sum % 9;
    cand += char(b+48);
    for(int q = 0; q < a; q++)
        {
        cand += '9';
        }
    max_cand = cand;
    max_cand[max_cand.length()-1] = cand[0];
    max_cand[0] = '9';
    }
int locate()
{
    for(int a = 0; a < cand.length()-1; a++)
    {
        if(cand[a] != '9')
        {
            inc_pos = a;
            //cout << inc_pos << " ";
        }
    }
}
int rev_loc()
{
    for(int a = cand.length()-2; a >= 0; a--)//search backwards for first non-9
    {
        if(cand[a] != '9')
        {
            first_pos = a;
            a = 0;
            //cout << "reverting to: " << first_pos << " ";
        }
    }
}
int main()
    {
    int steps = 0;
    bool step_flag = true;
    cout << "Palindromic Prime? ";
    cin >> sum;
    out1.open("candidates.txt", ios::out);
    cout << "Display each ___ candidates. (0 for none, 1 for all, 10 for every 10th, etc.)" << endl;
    cout << "Warning: Selecting 1 will result in slow execution for certain large primes." << endl;
    cin >> steps;
    if(steps == 0)
    {
             step_flag = false;
             }
    generate(); //determines lowest and highest candidates
    cout << counter << " " << cand << endl;
    out1 << cand << endl;
    cand[0]++; //increment to 2nd lowest candidate (special case)
    cand[1]--;
    counter++;
    if(steps == 1)
        {
        cout << counter << " " << cand << endl;
        }
    out1 << cand << endl;
    while(cand < max_cand)
        {
        while(cand[cand.length()-1] == '9')//we are iterating through a run of 89 swaps
            {
            locate();
            inc(inc_pos);
            counter++;
            if(step_flag && counter % steps == 0)
                {
                cout << counter << " " << cand << endl;
                }
            out1 << cand << endl;
            }
        rev_loc(); //undo all of the swaps
        cand[first_pos]++; //increase the last non-9 number
        cand[first_pos+1] = cand[cand.length()-1]; //put the last digit
        cand[first_pos+1]--;
        if(first_pos+1 != cand.length()-1)
            {
                cand[cand.length()-1] = '9'; //put the last 9 back
            }
        counter++;
        if(step_flag && counter % steps == 0)
        {
        cout << counter << " " << cand << endl;
        }
        out1 << cand << endl;
        test_sum = 0;
        }
out1.close();
cout << "Finished at: " << counter << " " << cand << endl;
_getch();
}