Ответ на задачу

[vak]

Задачку про увеличение числа в N раз при перестановке задней цифры вперёд я предложил с умыслом. Хотелось показать, как работать в Си++ с целыми числами неограниченной разрядности. Есть такая библиотека GMP. Написана она на Си, но имеет также интерфейс Си++. Вот программа, которая вычисляет ответы для каждого из N.

#include <iostream>
#include <gmpxx.h>

using bigint = mpz_class; // Integer type with unlimited precision

int main()
{
    for (int n = 2; n < 10; n++) {
        bigint ten_pow_k = 1;
        for (int k = 1; k < 100; k++) {
            ten_pow_k *= 10;
            bigint x = n * (ten_pow_k - n);
            if (x % (10*n - 1) == 0) {
                bigint v = 10*x / (10*n - 1) + n;
                std::cout << n << " * " << v << " = " << (n * v) << '\n';
                break;
            }
        }
    }
}

В библиотеке тип неограниченного целого называется mpz_class. Я переобзываю его bigint для большей ясности. Значения этого типа ведут себя ровно так же, как обычные int.

Компилируем, запускаем:

$ c++ -std=c++17 n-times.cpp -o n-times `pkg-config gmpxx --cflags --libs`
$ ./n-times
2 * 105263157894736842 = 210526315789473684
3 * 1034482758620689655172413793 = 3103448275862068965517241379
4 * 102564 = 410256
5 * 102040816326530612244897959183673469387755 = 510204081632653061224489795918367346938775
6 * 1016949152542372881355932203389830508474576271186440677966 = 6101694915254237288135593220338983050847457627118644067796
7 * 1014492753623188405797 = 7101449275362318840579
8 * 1012658227848 = 8101265822784
9 * 10112359550561797752808988764044943820224719 = 91011235955056179775280898876404494382022471

Comments

[spamsink]

В Boost же всё это есть.

[vak]

Boost как раз и использует GMP для своего gmp_int.

[ircicq]

В своё время использовал MPIR - оптимизированный форк GMP.
К сожалению, его прекратили развивать

[vak]

Вероятно, влили все оптимизации обратно в GMP.

[lxe]

Оно жпль же.

[vak]

LGPL.
https://en.wikipedia.org/wiki/GNU_Lesser_General_Public_License

[lxe]

Borderline kosher.

[vak]

Куча коммерческого софта использует libgmp.

[lxe]

Я знаю. Но рассуждаю с т/з инди-разработчика, у которого в гараже нет места на второй письменный стол для адвоката.
Ну, и common law-фундаменталиста, конечно.
Все, что я делаю сам, я выкладываю под (0).

[vak]

Я тоже предпочитаю свободные лицензии BSD/MIT/Apache. Но тут уж исторически сложилось. Единственное отличие: правки в LGPL коде нельзя захомячить. Обязан выкладывать в оперсорс.

[lxe]

Так я в претензии разве. Вздыхаю, не более (и зарубаю на будущее).

Сейчас пилю для Rakko Windows-реализации разных POSIX APIs. (Нет, не fork(). Хотя вопрос изучил.)
Тоже все под (0).

[malyj_gorgan]

Понапридумували всякого, блін
Я якось на співбесіді вирішив перевірити логіку кандидата -- попросив написати функцію для обчислення і виводу v форматі десяткових регістрів факторіала. Ну, там, типу 20! = 2,432,902,008,176,640,000
Хотів подивитися, як людина зі списками буде гратися. А, виявляється, в Python'і ма той час розмір інтеджера був довільний, а не чотири байти.
Я аж на пітонівський кодерпад образився

[vak]

На Пітоні все занадто легко. 😀
Пітонівське рішення для цієї задачки у мене давно мається.

https://github.com/sergev/vak-opensource/blob/master/languages/python/problem-xn.py

[sassa_nf]

як приклад використання gmp, годиться

але для розв'язку цієї задачі довгої арифметики не потрібно

> 5 * 102040816326530612244897959183673469387755 = 510204081632653061224489795918367346938775

(не кажучи вже про те, що для 5 є значно менше число, ніж видане у цьому дописі)

[vak]

Яке число для пʼяти?

[sassa_nf]

142857 * 5 = 714285

[sassa_nf]

Щось ніхто не зацікавився, як без довгої арифметики розв'язувати.

Справа в тому, що всі цифри числа повністю визначаються N та останньою цифрою. Тоді можна знайти всі цифри для кожної можливої останньої цифри, і обрати послідовність, яка дасть найменше число - звісно, витримуючи додаткові умови, що число не може починатись на нуль.

Що мене вразило, так це що такі числа існують для всіх останніх цифр - тобто, що цикл завжди містить в собі останню цифру.

А коли я подивився на розв'язання із довгою арифметикою, то здивувався, що майже для всіх N цей підхід знайшов справді найменші числа. Дивне тут те, що у формулі ніщо не вказує, що таким чином ми отримаємо найменше із можливих чисел. У обговоренні на maths stackexchange теж нічого про це немає. Можна лише зауважити, що для 9 справді цей метод знаходить найменше число, бо 1 - єдина перша цифра, яка при множенні на N=9 не подовжує число. Тому найстарший розряд 1, і відповідно остання цифра 9. А про інші N такого не можна сказати - не можна сказати, що тільки N підходить як остання цифра.