#include <QCoreApplication>
#include <QDebug>
#include <QList>
#include <QtMath>
#include <QElapsedTimer>

QList<quint64> primeList = {2,3,5,7,11};
quint64 maxLevel = 1;
quint64 update = 1000000;

quint64 nextPrime() {
    quint64 lastPrime = primeList.last();
    quint64 testNumber = lastPrime + 2;
    quint64 limit = qCeil(qSqrt(testNumber));
    quint64 index = 0;
    while(true) {
        if (testNumber % primeList.at(index) == 0) {
            testNumber += 2;
            limit = qCeil(qSqrt(testNumber));
            index = 0;
        } else if (index < primeList.count() && primeList.at(index) <= limit) {
            index++;
        } else {
            primeList.append(testNumber);
            return testNumber;
        }
    }
}

QList<quint64> getDecomposition(quint64 number) {
    QList<quint64> decomp;
    quint64 index = 0;
    quint64 limit = qCeil(qSqrt(number));
    while(number > 1) {
        quint64 prime;
        if (index >= primeList.count()) {
            prime = nextPrime();
        } else {
            prime = primeList[index];
        }
        if (primeList.contains(number) || prime > limit) {
            decomp.append(number);
            number = 1;
        } else if (number % prime == 0) {
            decomp.append(prime);
            number /= prime;
            limit = qCeil(qSqrt(number));
        } else {
            index++;
        }
    }
    return decomp;
}

QString recompose(QList<quint64> decomp, quint64 base = 10) {
    QString result = "";
    quint64 countRepeat = 1;
    quint64 previous = -1;
    for (quint64 i = 0; i < decomp.count(); i++) {
        quint64 prime = decomp[i];
        if (previous != prime) {
            if (countRepeat > 1) {
                result += QString::number(countRepeat, base);
            }
            countRepeat = 1;
            result += QString::number(prime, base);
            previous = prime;
        } else {
            countRepeat++;
        }
    }
    if (countRepeat > 1) {
        result += QString::number(countRepeat, base);
    }
    return result;
}

QString niceDecomp(QList<quint64> decomp, quint64 b) {
    QString result = "";
    quint64 countRepeat = 1;
    quint64 previous = -1;
    for (quint64 i = 0; i < decomp.count(); i++) {
        quint64 prime = decomp[i];
        if (previous != prime) {
            if (countRepeat > 1) {
                result += "^" + QString::number(countRepeat, b);
            }
            countRepeat = 1;
            if (!result.isEmpty()) {
                result += " x ";
            }
            result += QString::number(prime, b);
            previous = prime;
        } else {
            countRepeat++;
        }
    }
    if (countRepeat > 1) {
        result += "^" + QString::number(countRepeat, b);
    }
    return result;
}

bool check(quint64 i, QList<quint64> decomp, quint64 b, quint64 objective, quint64 level) {
    quint64  parsed = recompose(decomp, b).toInt(Q_NULLPTR, b);
    bool subresult = false;
    if (i > parsed && level < maxLevel) {
        QList<quint64> nextdecomp = getDecomposition(parsed);
        subresult = check(parsed, nextdecomp, b, i, level + 1);
    }
    if (subresult || (decomp.count() > 1 && objective == parsed)) {
        qDebug() << "* BASE:" << b << ":  \t"
                 << qPrintable(QString::number(i, b)) << qPrintable("(" + QString::number(i) + ")") << qPrintable("=")
                 << qPrintable(niceDecomp(decomp, b)) << qPrintable("(" + niceDecomp(decomp, 10) + ")");
        return true;
    }
    return false;
}

void find(quint64 start, quint64 max, quint64 minbase, quint64 maxBase) {
    QElapsedTimer timer;
    timer.start();
    int previousElapsed;
    for (quint64 i = start; i < max; i++) {
        QList<quint64> decomp = getDecomposition(i);
        if (i % update == 0) {
            qDebug() << i << "took" << timer.elapsed() - previousElapsed << "\tprime count"
                     << primeList.count() << "\tbiggest prime" << primeList.last() << "\telapsed" << timer.elapsed();
            previousElapsed = timer.elapsed();
        }
        for (quint64 b = minbase; b <= maxBase; b++) {
            check(i, decomp, b, i, 0);
        }
    }
    qDebug() << "FINISH: from" << start << "to" << max << "in base" << minbase << "to" << maxBase << "took" << timer.elapsed() / 1000 << "seconds";
}

int main(int argc, char *argv[])
{
    Q_UNUSED(argc)
    Q_UNUSED(argv)
    find(1, UINT64_MAX, 2, 36);
    return 0;
}