Наименьшее число, имеющее только 0 и 4 в качестве цифр

Ответ 1

Если я понимаю проблему, решения должны соответствовать выражению regualr 0 | 4 + 0 *

Это манит время, когда я не программирую на C, но следующий код может сделать трюк.

int calc( int n ) {
  int factor5;
  int factor2;
  int j;
  int a;
  int b;
  int i;

  /* trivial case 0 result is 0 */
  if( n==0 ) return 0;

  /* find the number of factors 2 and 5 in n */
  for( a=n, factor5=0; a%5==0; a/=5, factor5++ ); 
  for( a=n, factor2=0; a%2==0; a/=2, factor2++ ); 

  /* result is r=b*a where a=2^(j+2)*5^j */
  j=factor5;
  if( j < factor2-2 ) j=factor2-2; 

  for( a=4,i=0; i<j; i++, a*=10 ); 

  /* generate b in 1, 11, 111, ... until solution found */ 
  for( b=1; (a*b)%n!=0; b=10*b+1 );
  return a*b;
}

он может быть протестирован с помощью:

int main ( void ) {
  int n,r;

  for( n=0; n<10; n++) {
    r=calc(n); printf( "n=%d r=%d\n", n, r );
  }

  return 0;
}

Примечание. Оптимизируйте его. Также замените "int" на "long", "long long" или используйте библиотекарь любых целых чисел.

Тесты:

n=0 r=0
n=1 r=4
n=2 r=4
n=3 r=444
n=4 r=4
n=5 r=40
n=6 r=444
n=7 r=444444
n=8 r=40
n=9 r=444444444

Rationalle:

В дополнение к тривиальному случаю 0 с результатом 0 результат "r" должен соответствовать регулярному выражению "4 + 0 *": четыре с последующими нулями. То есть в нормальной арифметике r = x * 10 ^ j, где x - в 4,44,444,....

Если мы выберем коэффициент 4, то в последовательности 1, 11, 111,... имеем r = x * 4 * 10 ^ j с x. Обратите внимание, что цифры в этой последовательности никогда не имеют коэффициентов 2 и 5 (они не равны даже числам и не заканчиваются на 0 или 5).

В заключение, r = x * 2 ^ (j + 2) * 5 ^ j, с x в 1, 11, 111,... и "j", полученным из факторизации аргумента. На первом этапе программы вычисляется "j", затем вычисляем a = 2 ^ (j + 2) * 5 ^ j и, наконец, генерируем последовательность 1, 11, 111,... и проверяем ее до первого действительного результата.

Ответ 2

Позвоните по 40-значению C, т.е. C = A x B.

Учитывая ограничения, которые я их понимаю, это делает C = AxB из языка 4^n 0^m (не читайте это как 4 к мощности n, он должен означать повторение 4 n раз), поэтому нам нужно только n и m описать C.

Замечания:

• Поиск наименьшего B эквивалентен поиску наименьшего C, который кратен A.
• Когда два C -значений имеют различное количество цифр, C с большим числом цифр больше.
• Если два C -значения имеют равное количество цифр n + m, C с большим числом 4 больше.

Следовательно, мы зацикливаем число цифр в C (начиная с 1 и увеличивая) и на число 4 в C с фиксированным числом цифр, снова начиная с одного 4 и увеличиваться. Это дает нам все возможные числа C в численном порядке.

Как указано и введено в ответ @pasaba por aqui, можно уменьшить пространство поиска, используя тот факт, что A и C могут делиться основными факторами. В этом случае каждый C всегда, по крайней мере, имеет простой коэффициент 2 (2^2 = 4) и, возможно, 5 (2*5 = 10).

Действительно, C = x * 2^(j + 2) * 5^j с x in [1, 11, 111, ...] (т.е. C = x * 4 * 10^j). Наименьший j равен наибольшему числу факторов 2 или 5 в A. Например. если A % 25 == 0, j должно быть 2, если A % 400 == 0, j должно быть 4 и т.д.

См. pasaba por aqui ответ для этого решения.

Версия для грубой силы:

#include <cstdint>
#include <iostream>


int
main(int, char *[])
{
    // use uintmax_t and hope that the number still fits.
    uintmax_t = 13ul; // or whatever

    for (unsigned k = 1u;; ++k) {
        // k is the number of digits
        for (unsigned m = 1u; m <= k; ++m) {
            // m is the number of 4s. 
            // We start at one 4 (zero does not make sense)
            uintmax_t C = 0u;
            // build C, add as many 4s as requested and
            // fill up with zeros
            for (unsigned i = 0; i < k; ++i) {
                if (i < m) {
                    C = C * 10 + 4;
                } else {
                    C = C * 10;
                }
            }
            // check if we have a multiple of A
            if (C % A == 0) {
                std::cout << "C = " << C << std::endl;
                std::cout << "B = " << (C / A) << std::endl;
                return 0;
            }
        }
    }

    return 1;
}

Ответ 3

Здесь я даю эффективный алгоритм, то есть тот, который работает во времени (редактирование: исправление) многочленом в значении А для решения вопроса о числе А. Я также даю доказательство того, что это число N существует для всех чисел А и доказать правильность моего алгоритма - доказательство показывает, что для любого числа A правильный ответ имеет в нем не более A ^ 2 4 (и число нулей не более чем вдвое превышает число цифр A, грубо), (Я не знаю, является ли луч A ^ 2 четверой, но я думаю, что это, вероятно, не слишком далеко). Время работы не будет больше полиномиального размера A или выхода. (Я не совсем это понял.) Увидев другие ответы сейчас, это в основном то же самое, что и pasaba por aqui, но я думаю, что я даю более строгие объяснения, почему это работает. (Хотя мое письмо может быть улучшено, вероятно...)

Терминология: В дальнейшем я скажу, что a number N has the form {STRING} означает, что это десятичное расширение соответствует регулярному выражению {STRING}, хотя это не стандартная терминология терминов.

Задача: Учитывая A, Найдите наименьшее целое число N вида "4 + 0 *" такое, что N mod A = 0

Шаг 1: Рассмотрим 10 mod A и, в частности, последовательность {10 ^ n mod A} для n = 1,2,3,...

Первый очевидный вопрос: что произойдет, если 10 - обратимый mod A, т.е. 10 является взаимно простым для A, а если нет. (Edit: это на самом деле не очевидно, но в 90% этих элементов элементарной теории чисел путь к успеху состоит в том, чтобы сделать некоторый анализ случаев, основанный на первичной факторизации чисел, и думать о том, когда все происходит взаимно, они имеют общие факторы, часто являются хорошим направлением.)

Если 10 не является совпадающим с A, существует несколько возможностей. Один из них состоит в том, что 10 делит A, это глупый случай. Мы можем просто разделить А на 10, найти ответ тогда и умножить его на 10. Если это исключено, то либо 5 делит А, но 2 не делает, либо 2 делит А, а 5 не делает, или А является взаимно простой до 10.

Предположим, что 5 делит A, а 2 - нет. Если N mod A = 0 имеет вид выше, рассмотрим N mod 5 - он равен младшей строке с 5 | 10. Поэтому младший разряд должен быть 0, а не 4, поэтому 10 | N. В этом случае любое целое число вида "4 + 0 *" такое, что N mod A = 0, также имеет N mod 2A = 0. И 10 делит 2A, так что это означает, что мы можем свести к более простой задаче.

Предположим, что 2 делит A, а 5 - нет. Очевидно, что 4 фактически делит любое число формы "4 + 0 *", поэтому для любого нечетного числа A 'наименьшее целое число N, как описано, является тем же самым, считаем ли мы, что A является A', 2A 'или 4A ". Предположим теперь, что 8 делит A. Так как 8 делит любое число формы" 40+", а 8 не делит 4, аналогичным аргументом, как и прежде, следует, что число N должно иметь нуль в качестве нижней цифры, поэтому, если 8 | A, это означает, что если N mod A = 0, то также N mod 5A = 0. Таким образом, мы можем перейти к этому числу, а затем вытащить мощность 10 и свести к более простому вопросу.

Таким образом, мы можем ограничить внимание случаем, когда 10 взаимно прост в A.

Это упрощает, потому что тогда элементарная теория чисел (теорема китайского остатка) говорит нам, что 10 - обратимый mod A, т.е. 10 ^ k = 1 mod A для некоторого достаточно большого k. Это означает также, что мы можем игнорировать возможность нулей в цифрах N - так как если X * 10 ^ y = 0 mod A и 10 - обратимый mod A, мы должны также иметь, что X = 0 mod A, что быть меньшим решением.

Таким образом, как только 10 взаимно прост в A, наименьшее целое число N вида "4 + 0 *" такое, что N mod A = 0 совпадает с наименьшим целым числом вида "4+", для которого N mod A = 0.

(Кроме того, теперь ясно, что всегда существует НЕКОТОРНОЕ целое число N этой формы, которое делится на A. Таким образом, все эти программы действительно заканчиваются и не имеют бесконечного цикла для любого ввода:) Потому что мы можем сделать беспроигрышный анализ. Предположим, что 10 ^ k = 1 mod A. Теперь рассмотрим значение десятичного числа K, составленного из точно k 4, приведенного по модулю A. Если это ноль, то это доказывает, что число существует, и мы закончили. Если это не ноль, то скажем, что это некоторое значение "a" mod A, не равное 0. Мы знаем, что число K * 10 ^ k также равно "a" mod A, потому что 10 ^ k = 1 mod A. А K * 10 ^ k также имеет форму, о которой мы заботимся, и это верно и для K * 10 ^ {ik} для любого i. Таким образом, если взять десятичное число, составленное из точно A * k 4, оно должно быть равно A * a = 0 mod A. Таким образом, мы построили число N искомого вида, которое делится на A.)

Теперь мы можем решить проблему без грубой силы напрямую простым циклом. Мы просто отслеживаем значение "4000000... mod A" и значение "444444.... mod A", где цифры k-цифр длинны, и мы вычисляем эти значения по модулю для k + 1-разрядных чисел, умножая значение первого на значение 10 mod A, уменьшая по модулю A, затем добавляя это также ко второму и уменьшая по модулю A.

Здесь полный код:

#include <cassert>
#include <iostream>

typedef unsigned long long ul;

ul fast_finder(ul A) {
  assert(A);
  ul num_zeros = 0; // remember how many zeros we need to add at the end

  while ((A % 10) == 0) {
    A /= 10;
    ++num_zeros;
  }

  while ((A % 5) == 0) {
    A /= 5;
    ++num_zeros;
  }

  while ((A % 8) == 0) {
    A /= 2;
    ++num_zeros;
  }

  while ((A % 2) == 0) {
    A /= 2;
  }

  ul four_mod_A = 4 % A;
  ul ten_mod_A = 10 % A;

  ul num_fours = 1;
  // in these variable names "k" is the number of fours we are considering
  ul four_times_ten_to_the_k_mod_A = four_mod_A;
  ul sum_of_fours_mod_A = four_mod_A;
  while (sum_of_fours_mod_A) {
    four_times_ten_to_the_k_mod_A *= 10;
    four_times_ten_to_the_k_mod_A %= A;
    sum_of_fours_mod_A += four_times_ten_to_the_k_mod_A;
    sum_of_fours_mod_A %= A;
    ++num_fours;
  }

  // now build an integer representation of the result from num_fours, num_zeros
  ul result = 0;
  while (num_fours) {
    result *= 10;
    result += 4;
    --num_fours;
  }
  while (num_zeros) {
    result *= 10;
    --num_zeros;
  }
  return result;
}

// This is to check the correctness of the fast algorithm, it just the naive algorithm.
ul slow_finder(ul A) {
  assert(A);
  for (ul B = 1;;++B) {
    ul N = B * A;
    bool saw_four = false;
    while (N) {
      ul low = N % 10;
      if (low == 4) {
          saw_four = true;
      } else if (low != 0 || saw_four) { break; }
      N /= 10;
    }
    if (N == 0)
      return A*B;
  }
}

void check(ul x) {
  std::cout << x << ": ";
  ul f = fast_finder(x);
  std::cout << f << std::flush;
  ul s = slow_finder(x);
  if (f != s) {
    std::cout << "failed! ( " << s << " )" << std::endl; return;
  }
  std::cout << '.' << std::endl;
}

int main() {
  check(1);
  check(3);
  check(4);
  check(5);
  check(10);
  check(11);
  check(13);
  check(15);
  check(18);
  check(73);
  check(64);
  check(52);
}