Здравствуйте, Spiceman, Вы писали:

А можно идею алгоритма в кратце, а то не все понятно
Все же не очень быстро...
А почему списком?

У меня вышла вот такая вещь...

#include <stdio.h>
#include <string.h>
#include <vector>
#include <time.h>
// constants
const unsigned int BlockSize = 1023;
// group of digits
struct digitgroup
{
  digitgroup(): binary(0L) { }
  digitgroup(unsigned int bin): binary(bin) { }
  union
  {
    struct
    {
      unsigned char digit0: 4;
      unsigned char digit1: 4;
      unsigned char digit2: 4;
      unsigned char digit3: 4;
      unsigned char digit4: 4;
      unsigned char digit5: 4;
      unsigned char digit6: 4;
      unsigned char digit7: 4;
    };
    unsigned int binary;
  };
};
// block of digits
struct digitblock
{
  // create one block using carry value
  digitblock(unsigned char carry = 0)
  {
    for (int i = 0; i < BlockSize; groups[i++].binary = 0L);
    if (carry)
    {
      count = 1;
      groups[0].digit0 = 1;
    }
    else
      count = 0;
  }
  digitgroup groups[BlockSize];
  unsigned int count;
};
// vector of pointers to digit blocks
typedef std::vector<digitblock*> digitvector;
// temporary and total execution result
struct result
{
  result(): carry(0), zeros(0), maxzeros(0) { }
  unsigned char carry;
  unsigned short zeros;
  unsigned short maxzeros;
};
// multiply one digit
inline unsigned char multiply(unsigned char digit, result& r)
{
  // multiply digit
  digit <<= 1;
  digit += r.carry;
  // check carry
  if (digit > 9)
  {
    r.carry = 1;
    digit -= 10;
  }
  else
    r.carry = 0;
  // count zeros
  if (digit)
  {
    r.maxzeros = r.zeros > r.maxzeros ? r.zeros : r.maxzeros;
    r.zeros = 0;
  }
  else
    ++r.zeros;
  // return result
  return digit;
}
// multiply one digit group by two
inline void multiply(digitgroup& part, result& r)
{
  // mult digits
  part.digit0 = multiply(part.digit0, r);
  part.digit1 = multiply(part.digit1, r);
  part.digit2 = multiply(part.digit2, r);
  part.digit3 = multiply(part.digit3, r);
  part.digit4 = multiply(part.digit4, r);
  part.digit5 = multiply(part.digit5, r);
  part.digit6 = multiply(part.digit6, r);
  part.digit7 = multiply(part.digit7, r);
}

void multiply(digitblock& dblock, result& r)
{
  // multiply all groups in block
  for (digitgroup *i = dblock.groups, *end = dblock.groups + dblock.count; i != end; multiply(*(i++), r));
  // if we have carry and some free groups in block,
  // then initialize new group and clear carry
  if (r.carry && dblock.count < (BlockSize - 1))
  {
    dblock.groups[dblock.count++].digit0 = 1;
    r.carry = 0;
  }
}

void multiply(digitvector& digits, result& r)
{
  for (digitvector::iterator i = digits.begin(), end = digits.end(); i != end; multiply(**(i++), r));
  // if carriage taken out of last block, create, initialize and process new one
  if (r.carry)
  {
    digits.push_back(new digitblock());
    multiply(*(digits.back()), r);
  }
}

size_t digitscount(const digitvector& digits)
{
  if (!digits.size())
    return 0;
  // count full blocks, each block contains BlockSize groups, each group contains 8 digits
  size_t sz = (digits.size() - 1) * BlockSize * 8;
  // count full groups in last block which can't be empty, each group contains 8 digits
  sz += (digits.back()->count - 1) * 8;
  // count active digits in last group
  digitgroup &i = digits.back()->groups[digits.back()->count - 1];
  if (i.digit7) return sz+8;
  if (i.digit6) return sz+7;
  if (i.digit5) return sz+6;
  if (i.digit4) return sz+5;
  if (i.digit3) return sz+4;
  if (i.digit2) return sz+3;
  if (i.digit1) return sz+2;
  if (i.digit0) return sz+1;
  return sz;
}

void printtime(clock_t t)
{
  size_t msecs = t % CLOCKS_PER_SEC;
  size_t secs = (t / CLOCKS_PER_SEC) % 60;
  size_t mins = (t / CLOCKS_PER_SEC / 60) % 60;
  size_t hours = t / CLOCKS_PER_SEC / 3600;
  printf("[%02u:%02u:%02u.%03u]", hours, mins, secs, msecs);
}

void checkzeros(digitvector& digits, size_t& power, size_t& border, size_t zeros)
{
  for (result r = result(); r.maxzeros < zeros;)
  {
    r = result();
    power++;
    multiply(digits, r);
    if (!(power % border))
    {
      printf("Reached %u power of 2, %u digits total\n", power, digitscount(digits));
      border *= 10;
      fflush(stdout);
    }
  }
  printtime(clock());
  printf(" a(%u) = %u, %u digits total\n", zeros, power, digitscount(digits));
  fflush(stdout);
}

int main(int argc, char** argv)
{
  digitvector digits;
  digits.push_back(new digitblock(1));
  size_t power = 0;
  size_t border = 1000;
  size_t zeros = 1;
  while(true)
    checkzeros(digits, power, border, zeros++);
}

простенько до одури, но вроде работает
слегка оптимизировал работу с памятью за счёт блоков
результаты пока такие
[00:00:00.000] a(1) = 10, 4 digits total
[00:00:00.000] a(2) = 53, 16 digits total
[00:00:00.000] a(3) = 242, 73 digits total
[00:00:00.000] a(4) = 377, 114 digits total
Reached 1000 power of 2, 302 digits total
[00:00:00.000] a(5) = 1491, 449 digits total
[00:00:00.000] a(6) = 1492, 450 digits total
[00:00:00.062] a(7) = 6801, 2048 digits total
Reached 10000 power of 2, 3011 digits total
[00:00:00.296] a(8) = 14007, 4217 digits total
Reached 100000 power of 2, 30127 digits total
[00:00:15.734] a(9) = 100823, 30375 digits total
[00:08:06.140] a(10) = 559940, 168719 digits total

на шарпе никто не выкладывал?

Found KNumber 0 with power 1
Found KNumber 1 with power 10
Found KNumber 2 with power 61
Found KNumber 3 with power 271
Found KNumber 4 with power 583
      power 1000 calculated in 28 ms
Found KNumber 5 with power 1330
Found KNumber 6 with power 1492
      power 2000 calculated in 59 ms
      power 3000 calculated in 131 ms
      power 4000 calculated in 208 ms
      power 5000 calculated in 348 ms
      power 6000 calculated in 563 ms
Found KNumber 7 with power 6802
      power 7000 calculated in 817 ms
      power 8000 calculated in 963 ms
      power 9000 calculated in 1131 ms
      power 10000 calculated in 1315 ms
      power 11000 calculated in 1518 ms
      power 12000 calculated in 1742 ms
      power 13000 calculated in 1983 ms
      power 14000 calculated in 2246 ms
Found KNumber 8 with power 14007
      power 15000 calculated in 2526 ms
      power 16000 calculated in 2830 ms
      power 17000 calculated in 3149 ms
      power 18000 calculated in 3486 ms
      power 19000 calculated in 3849 ms
      power 20000 calculated in 4227 ms
      power 21000 calculated in 4623 ms
      power 22000 calculated in 5100 ms
      power 23000 calculated in 5559 ms
      power 24000 calculated in 6021 ms
      power 25000 calculated in 6494 ms
      power 26000 calculated in 6993 ms
      power 27000 calculated in 7505 ms
      power 28000 calculated in 8284 ms
      power 29000 calculated in 8838 ms
      power 30000 calculated in 9414 ms
      power 31000 calculated in 10021 ms
      power 32000 calculated in 10633 ms
      power 33000 calculated in 11272 ms
      power 34000 calculated in 11919 ms
      power 35000 calculated in 12587 ms
      power 36000 calculated in 13273 ms
      power 37000 calculated in 13982 ms
      power 38000 calculated in 14705 ms
      power 39000 calculated in 15452 ms
      power 40000 calculated in 16214 ms
      power 41000 calculated in 17008 ms

исходник (3.5)

using System.Collections.Generic;
using System;

using BytePair = System.Collections.Generic.KeyValuePair<byte, byte>;
using System.Diagnostics;
using System.Threading;

namespace KZero
{
    class KNumber
    {
        public int MaxZeroCount;
        public int Power;

        public byte[] NumberPairs;
    }

    class Program
    {
        private static readonly BytePair[] HexAddition = new BytePair[100 + 100];
        private static readonly bool[] HexAdditionExists = new bool[100 + 100];

        private static BytePair InitializeHexAdditionValue(byte val1, byte val2)
        {
            var reminder = (byte)((val1 + val2) % 100);
            var primary = (byte)((val1 + val2 - reminder) / 100);
            return new BytePair(primary, reminder);
        }

        private static int GetHexAdditionIndex(byte val1, byte val2)
        { 
            return val1 + val2;
        }

        private static BytePair GetHexAdditionValue(byte val1, byte val2)
        {
            var index = GetHexAdditionIndex(val1, val2);
            if (HexAdditionExists[index])
                return HexAddition[index];

            HexAdditionExists[index] = true;
            return HexAddition[index] = InitializeHexAdditionValue(val1, val2);
        }

        private static BytePair TripleAdd(byte val1, byte val2, byte val3)
        {
            if (val3 == 0)
            {
                return GetHexAdditionValue(val1, val2);
            }

            var pair1 = GetHexAdditionValue(val1, val2);
            var pair2 = GetHexAdditionValue(pair1.Value, val3);

            return new BytePair((byte)(pair1.Key + pair2.Key), pair2.Value);
        }

        static void Main()
        {
            const bool PrintOutput = false;
            //InitializeHexAddition();

            var kNumber = new KNumber { MaxZeroCount = 0, Power = 0, NumberPairs = new byte[] { 1 } };
            var kNumbers = new Dictionary<int, KNumber>();

            var watch = new Stopwatch();

            while (true)
            {
                watch.Start();
                kNumber = CalculateNextKNumber(kNumber);
                watch.Stop();

                if (kNumber.Power % 1000 == 0)
                    Console.WriteLine("      power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms");

                if (PrintOutput)
                {
                    Console.Write("Power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms - ");

                    var tmp = (byte[])kNumber.NumberPairs.Clone();
                    Array.Reverse(tmp);
                    Array.ForEach(tmp, b => Console.Write(b < 10 ? ("0" + b) : b.ToString()));
                    Console.WriteLine();
                    
                    Thread.Sleep(100);
                }

                if (kNumbers.ContainsKey(kNumber.MaxZeroCount))
                {
                    continue;
                }

                kNumbers[kNumber.MaxZeroCount] = kNumber;
                Console.WriteLine("Found KNumber " + kNumber.MaxZeroCount + " with power " + kNumber.Power);
            }
        }

        private static KNumber CalculateNextKNumber(KNumber seed)
        {
            var nextNumberPairsLength = seed.NumberPairs[seed.NumberPairs.Length - 1] == 0
                ? seed.NumberPairs.Length
                : seed.NumberPairs.Length + 1;

            var nextNumberPairs = new byte[nextNumberPairsLength];
            var kNumber = new KNumber { Power = seed.Power + 1, MaxZeroCount = 0 };

            var append = (byte)0;
            var i = 0;

            for (; i < seed.NumberPairs.Length; i++)
            {
                var val = seed.NumberPairs[i];
                var pair = TripleAdd(val, val, append);

                append = pair.Key;

                nextNumberPairs[i] = pair.Value;
            }

            if (append > 0)
            {
                nextNumberPairs[i] = append;
            }

            if (nextNumberPairs[nextNumberPairs.Length - 1] == 0)
            {
                var tmp = new byte[nextNumberPairs.Length - 1];
                Array.Copy(nextNumberPairs, tmp, tmp.Length);
                nextNumberPairs = tmp;
            }

            kNumber.NumberPairs = nextNumberPairs;
            CalculateMaxZeroCount(kNumber);

            return kNumber;
        }

        private static void CalculateMaxZeroCount(KNumber kNumber)
        {
            var currentZeroCount = 0;

            for (var i = 0; i < kNumber.NumberPairs.Length; ++i)
            {
                switch (kNumber.NumberPairs[i])
                {
                case 0:
                    currentZeroCount += 2;
                    break;
                case 10:
                    currentZeroCount += 1;
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    break;
                case 01:
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    if (i != kNumber.NumberPairs.Length - 1)
                    {
                        currentZeroCount = 1;
                    }
                    break;
                default:
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    currentZeroCount = 0;
                    break;
                }
            }
            UpdateKMaxZero(kNumber, currentZeroCount);
        }

        private static void UpdateKMaxZero(KNumber kNumber, int count)
        {
            if (count > kNumber.MaxZeroCount)
                kNumber.MaxZeroCount = count;
        }
    }
}

нет, нули считает неправильно скипаем for now

теперь правильно..

Found KNumber 0 with power 1, Number calculated in 3 ms is: 02
Found KNumber 1 with power 10, Number calculated in 3 ms is: 1024
Found KNumber 2 with power 53, Number calculated in 3 ms is: 9007199254740992
Found KNumber 3 with power 242, Number calculated in 3 ms is: 07067388259113537318333190...
Found KNumber 4 with power 377, Number calculated in 4 ms is: 307828173409331868845930000...
Found KNumber 5 with power 1491, Number calculated in 16 ms is: 068505199434441481928960132734923...
Found KNumber 6 with power 1492, Number calculated in 16 ms is: 1370103988688829638579202654698471015372
Found KNumber 7 with power 6801, Number calculated in 242 ms is: 20183687373087460349606707870495174...
Found KNumber 8 with power 14007, Number calculated in 1023 ms is: 33662724701763990788983568556041...
Found KNumber 9 with power 100823, Number calculated in 55332 ms is: 558795409300670784...

считалось на P4 2.6GHz, 3GB Ram

using System.Collections.Generic;
using System;

using BytePair = System.Collections.Generic.KeyValuePair<byte, byte>;
using System.Diagnostics;

namespace KZero
{
    class KNumber
    {
        public int MaxZeroCount;
        public int Power;

        public byte[] NumberPairs;
    }

    class Program
    {
        #region stuff
        private static readonly BytePair[] HexAddition = new BytePair[100 + 100];
        private static readonly bool[] HexAdditionExists = new bool[100 + 100];

        private static BytePair InitializeHexAdditionValue(byte val1, byte val2)
        {
            var reminder = (byte)((val1 + val2) % 100);
            var primary = (byte)((val1 + val2 - reminder) / 100);
            return new BytePair(primary, reminder);
        }

        private static int GetHexAdditionIndex(byte val1, byte val2)
        {
            return val1 + val2;
        }

        private static BytePair GetHexAdditionValue(byte val1, byte val2)
        {
            var index = GetHexAdditionIndex(val1, val2);
            if (HexAdditionExists[index])
                return HexAddition[index];

            HexAdditionExists[index] = true;
            return HexAddition[index] = InitializeHexAdditionValue(val1, val2);
        }

        private static BytePair TripleAdd(byte val1, byte val2, byte val3)
        {
            if (val3 == 0)
            {
                return GetHexAdditionValue(val1, val2);
            }

            var pair1 = GetHexAdditionValue(val1, val2);
            var pair2 = GetHexAdditionValue(pair1.Value, val3);

            return new BytePair((byte)(pair1.Key + pair2.Key), pair2.Value);
        }

        private static void PrintNumber(Stopwatch watch, KNumber kNumber)
        {
            Console.WriteLine("Found KNumber " + kNumber.MaxZeroCount + " with power " + kNumber.Power);
            Console.Write("Number calculated in " + watch.ElapsedMilliseconds + " ms is: ");

            var tmp = (byte[])kNumber.NumberPairs.Clone();
            Array.Reverse(tmp);
            Array.ForEach(tmp, b => Console.Write(b < 10 ? ("0" + b) : b.ToString()));
            Console.WriteLine();
        }

        #endregion stuff

        static void Main()
        {
            var kNumber = new KNumber { MaxZeroCount = 0, Power = 0, NumberPairs = new byte[] { 1 } };
            var kNumbers = new Dictionary<int, KNumber>();

            var watch = new Stopwatch();

            while (true)
            {
                watch.Start();
                kNumber = CalculateNextKNumber(kNumber);
                watch.Stop();

                if (kNumber.Power % 1000 == 0)
                    Console.WriteLine("      power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms");

                if (kNumbers.ContainsKey(kNumber.MaxZeroCount)) {
                    continue;
                }

                kNumbers[kNumber.MaxZeroCount] = kNumber;
                PrintNumber(watch, kNumber);
            }
        }

        private static KNumber CalculateNextKNumber(KNumber seed)
        {
            var nextNumberPairs = new byte[seed.NumberPairs.Length + 1];
            var kNumber = new KNumber { Power = seed.Power + 1, MaxZeroCount = 0 };

            var append = (byte)0;
            var i = 0;

            for (; i < seed.NumberPairs.Length; i++)
            {
                var val = seed.NumberPairs[i];
                var pair = TripleAdd(val, val, append);

                append = pair.Key;

                nextNumberPairs[i] = pair.Value;
            }

            if (append > 0)
            {
                nextNumberPairs[i] = append;
            }

            if (nextNumberPairs[nextNumberPairs.Length - 1] == 0)
            {
                var tmp = new byte[nextNumberPairs.Length - 1];
                Array.Copy(nextNumberPairs, tmp, tmp.Length);
                nextNumberPairs = tmp;
            }

            kNumber.NumberPairs = nextNumberPairs;
            CalculateMaxZeroCount(kNumber);

            return kNumber;
        }

        private static void CalculateMaxZeroCount(KNumber kNumber)
        {
            var currentZeroCount = 0;

            for (var i = 0; i < kNumber.NumberPairs.Length; ++i)
            {
                switch (kNumber.NumberPairs[i])
                {
                case 0:
                    currentZeroCount += 2;
                    break;
                case 10:case 20:case 30:case 40:case 50:case 60:case 70:case 80:case 90:
                    currentZeroCount += 1;
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    currentZeroCount = 0;
                    break;
                case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    if (i != kNumber.NumberPairs.Length - 1)
                    {
                        currentZeroCount = 1;
                    }
                    break;
                default:
                    UpdateKMaxZero(kNumber, currentZeroCount);
                    currentZeroCount = 0;
                    break;
                }
            }
            UpdateKMaxZero(kNumber, currentZeroCount);
        }

        private static void UpdateKMaxZero(KNumber kNumber, int count)
        {
            if (count > kNumber.MaxZeroCount)
                kNumber.MaxZeroCount = count;
        }
    }
}

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Spiceman, Вы писали:

S>А можно идею алгоритма в кратце, а то не все понятно
Да вобщем-то идея примерно та же, что у Pro100Oleh-а. Представляем число в 10-ричной системе, если ищем 1 ноль, в 100-ричной системе, если ищем 2 ноля, и т.д. Число у меня список (начиная с младших разрядов) — например, 512 = (2 1 5), 1024 = (4 2 0 1), 2^53 = (92 09 74 54 92 19 07 90). В таком списке довольно просто найти k нолей подряд. Это так, если:
1. элемент списка равен 0, либо
2. элемент списка (начиная с единиц, то есть слева) меньше 10^m и следующий элемент кратен 10^m. Например, для 2^53 элемент 07 < 10 и 90 кратно 10. m подбирается минимальным.

S>Все же не очень быстро...
Ну я не спец в лиспе, не знаю библиотек и функций. Написал как смог. Спецы, думаю, оптимизировали бы лучше. Теперь попробую тоже на C#

S>А почему списком?
Так получилось

Здравствуйте, Spiceman, Вы писали:

S>Здравствуйте, Seon, Вы писали:

S>>Здравствуйте, Spiceman, Вы писали:

S>>А можно идею алгоритма в кратце, а то не все понятно
S>Да вобщем-то идея примерно та же, что у Pro100Oleh-а. Представляем число в 10-ричной системе, если ищем 1 ноль, в 100-ричной системе, если ищем 2 ноля, и т.д. Число у меня список (начиная с младших разрядов) — например, 512 = (2 1 5), 1024 = (4 2 0 1), 2^53 = (92 09 74 54 92 19 07 90). В таком списке довольно просто найти k нолей подряд. Это так, если:
S>1. элемент списка равен 0, либо
S>2. элемент списка (начиная с единиц, то есть слева) меньше 10^m и следующий элемент кратен 10^m. Например, для 2^53 элемент 07 < 10 и 90 кратно 10. m подбирается минимальным.

S>>Все же не очень быстро...
S>Ну я не спец в лиспе, не знаю библиотек и функций. Написал как смог. Спецы, думаю, оптимизировали бы лучше. Теперь попробую тоже на C#

S>>А почему списком?
S>Так получилось

Принципиальный вопрос:
в вашем варианте есть перевод из 2-й в десятичную, или сразу работаете в десятичной?
умножаете 10-тичные числа или 2-ичные?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>Этюд для программиста.
V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>Найти a(1),...,a(7).

А>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)

А>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"


Подобная задача, по-моему, вошла в сборник всероссийских (или всесоюзных?) математических олимпиад (такая красненькая книжка). И решение там было такое же. Я всегда думал, что только с этого "конца" задачу и можно решить, но вроде бы можно и с другого...

Теорема Эйлера
a^φ(m)-1 = 0 (mod m), где φ(m) = m(1 — 1/p1)(1 — 1/p2)...(1 — 1/pk) и a и m взаимно простые.

В нашем случае имеем:

2^φ(5^k)-1=0 (mod 5^k)

φ(5^k)=5^(k-1)*4

2^(5^(k-1)*4+k)=2^k (mod 10^k)

2^k содержит приблизительно k*lg(2) десятичных знаков
Значит,2^(5^(k-1)*4+k) имеем как минимум k*(1-lg(2)) подряд идущих нулей.

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
B>Представим 2^n в виде a*10^k + b (b — остаток от деления на 10^k).
B>Я говорю, что есть такое m при которых b содержит k нулей. В моем случае b = g(x).
B>И доказываю, что cуществует n, такое что 2^n можно представить в такой форме. В моем случае n=f(m)-1.
B>Чтобы доказать возможность представления 2^n в такой форме, я доказываю, что при заданных целых b и 2^n, вычисленных по этим формулам, частное "a" тоже будет целым.

Это все понятно. Я тебя про другое, по-моему, спрашивал.

B>>>в) (16^y — 1) делится на 5y, т.к.
V>>Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется).
B>Я об этом говорил. y = 5^(m-1), а следовательно нечетно.
B>А пример не подходит, т.к. 13 не является степенью 5.

И где ты в своем доказательстве того, что 16^y-1 делится на 5y использовал, что y нечетное, или что оно является степенью 5? Вот твое доказательство:

16^y — 1 = (15+1)^y — 1,
т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем),
а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y

Здравствуйте, Аноним, Вы писали:
А>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)

А>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"

Выделенное не понял.

Здравствуйте, vadimcher, Вы писали:

V>И где ты в своем доказательстве того, что 16^y-1 делится на 5y использовал, что y нечетное, или что оно является степенью 5? Вот твое доказательство:
V>

V>16^y — 1 = (15+1)^y — 1,
V>т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем),
V>а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y

Да уж. Действительно. Я перечитал это еще раз и ужаснулся
Вообще я изначально доказывал это высказывание, подсчитывая количество множителей 5 в каждом члене выражения (15+1)^y — 1, где y=5^n. Потом меня "осенило", нашел более простое "доказательство" , ну т.е. то, которое я написал. Но, действительно, это не только ничего не доказывает, но и неверно в принципе. Благо, что ответ оказался все же верен.

Исправляю ошибку. Докажем, что 16^y — 1 делится на 5y, где y = 5^n.
Более простое доказательство на основе теоремы Эйлера (к сожалению, я ее не знал, ээх!).

Теорема Эйлера: a^ф(m) === 1 (mod m), ф - функция Эйлера, a и m взаимно просты
ф имеет следующее свойство: ф(p^n) = (p-1)*p^(n-1), когда p - простое

Доказать, что
16^(5^n) - 1 === 0 (mod 5*5^n))
Преобразовываем
2^(4*5^n) === 1 (mod 5^(n+1))
На основе указанного свойства ф, т.к. 5 - простое:
ф(5^(n+1)) = 4*5^n,
Отсюда:
2^(4*5^n) === 1 (mod 5^(n+1)) ч.т.д.

V>>>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
V>Это все понятно. Я тебя про другое, по-моему, спрашивал.

Я все-таки не совсем понял, о чем идет речь.
Что значит верны? Речь об этом?

Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
Количество возможных остатков равно f(k)
Последний неповторяющийся остаток равен g(k)

Это можно доказать.

Здравствуйте, Beam, Вы писали:

B>Исправляю ошибку. Докажем, что 16^y — 1 делится на 5y, где y = 5^n.
B>Более простое доказательство на основе теоремы Эйлера (к сожалению, я ее не знал, ээх!).

Да, именно теоремой Эйлера проще всего доказывать. Просто я хотел обратить твое внимание, что утверждение неверно не только для четных y, но и для многих нечетных, как, например, 13.

B>Я все-таки не совсем понял, о чем идет речь.
B>Что значит верны? Речь об этом?

B>

B>Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
B>Количество возможных остатков равно f(k)
B>Последний неповторяющийся остаток равен g(k)
B>

B>Это можно доказать.

Да, именно об этом. Просто в итоге ты использовал конкретные выражения для того, чтобы привести пример остатка (g(m)) при делении некоторой большой степени двойки (f(m)-1) на 10^m. Т.е., как я написал до этого, в твоем доказательстве не важно, действительно ли f() и g() выражают то, с чего ты начал. Т.е. для доказательства это не важно. Тем не менее, просто интересно.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, Аноним, Вы писали:
А>>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)

А>>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"

V>Выделенное не понял.



Ну, как я уже говорил, это вопрос с бородой. Поэтому автор поста написал схематично, опуская детали.

Между прочим, а что имелось в виду
в условиях задачи: ровно k нулей и на к-ом месте не ноль или имелось в виду как минимум к нулей? Если ровно k нулей, то через теорему Эйлера ответ получить
будет тяжело.

Теперь расшифрую Анонима.

Можно доказать более сильное утверждение: для любого натурального числа найдётся степень двойки, которая на него начинается.
Из этого утверждения всё следует.

Докажем это более сильное утверждение.
Пусть какая-то степень двойки начинается на x, тогда для некоторого m выполняется
x*10^m < 2^n <x*10^m+10^m-1.

Таким образом, задачу свелась к следующему: для данного x найти m и n, удовлетворяющие
x*10^m < 2^n <x*10^m+10^m-1
или
n*ln(2)<ln(x*10^m+10^m-1) и ln(x)+ln(10)*m < ln(2)*n

Значит, мы ищем целое число n в интервале ( ln(x)/ln(2)+ln(10)*m/ln(2), ln(x*10^m+10^m-1)/ln(2) )

При больших m ln(x*10^m+10^(m-1)) < ln(x*10^m+10^m-1), поэтому если мы найдём число n в меньшем интервале

( ln(x)/ln(2)+ln(10)*m/ln(2), ln(x*10^m+10^(m-1))/ln(2) ) = ( ln(x) / ln(2)+ln(10)*m/ln(2), m *ln(10)/ln(2)+ ln(x+1/10)/ln(2) ),

то оно подавно будет принадлежать большему.

Если обозначить очевидно иррациональное число ln(10)/ln(2) через alpha, ln(x) / ln(2) через x1, ln(x+1/10)/ln(2) через
x2, то получаем

Найти m и n такие, что

alpha *m-n лежит в (x1, x2)

А это можно доказать самому. Например, через теорему Лиувилля о приближении иррационального числа рациональной дробью.

Или из Вейля, или как-то ещё.


Что-то получилось многословно. Я помню решение в сборнике олимпиадных задач было совсем короткое...
Но задавать такие задачи детям... Есть в этом что-то садистское.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:
V>>Здравствуйте, Аноним, Вы писали:
А>>>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)
А>>>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"
V>>Выделенное не понял.

Выделенное я не понял, потому как оно кажется мне неверным. А автор в ответе писал это так, как будто это очевидно. Мне нет. Потому я переспросил.

А>Ну, как я уже говорил, это вопрос с бородой. Поэтому автор поста написал схематично, опуская детали.

Ну с бородой, или нет -- я не знаю. Это мне напоминает, как когда кто-то что-то постит, и обязательно найдется кто-нибудь: "баян!". Баян (по определению ) -- шутка, которую постоянно все пересказывают, и которая уже всем уши пробаянила, а если кто-то что-то там постил три года назад, то это не баян. Не надо путать "небаянность" и "уникальность" сообщения.

Короче, для меня эта задача новая, а потому просто интересно ее красивое решение. Так, в копилку. Я пока видел здесь два таких. Оба в итоге доказываются с помощью теоремы Эйлера. Просто и красиво! Это же решение также выглядит правильным, за исключением того, что вместо того, чтобы говорить, что тут все очевидно, надо было просто аккуратнее написать, что именно доказывается. Видимо, ты как раз и расписал это ниже. Спасибо.

А>Между прочим, а что имелось в виду
А>в условиях задачи: ровно k нулей и на к-ом месте не ноль или имелось в виду как минимум к нулей? Если ровно k нулей, то через теорему Эйлера ответ получить будет тяжело.

Имелось в виду "как минимум", но вторая интерпретация тоже интересная.

А>Теперь расшифрую Анонима.
А>Можно доказать более сильное утверждение: для любого натурального числа найдётся степень двойки, которая на него начинается.
А>Из этого утверждения всё следует.
А>Докажем это более сильное утверждение.
А>Пусть какая-то степень двойки начинается на x, тогда для некоторого m выполняется
А>x*10^m < 2^n <x*10^m+10^m-1
[]
А>Если обозначить очевидно иррациональное число ln(10)/ln(2) через alpha, ln(x) / ln(2) через x1, ln(x+1/10)/ln(2) через
А>x2, то получаем
А>Найти m и n такие, что
А>alpha *m-n лежит в (x1, x2)
А>А это можно доказать самому. Например, через теорему Лиувилля о приближении иррационального числа рациональной дробью.

n-ln(10)/ln(2)*m в (ln(x)/ln(2),ln(x+1/10)/ln(2))
Это утверждение совсем не то, что было в том топике. Поэтому это не пояснение к тому, а скорее попытка решить тем же путем.

Здравствуйте, vadimcher.
После нового года я постараюсь выложить и саму олимпиадную задачу и решение из сборника задач.

Заодно узнаем насколько она старая.

Здравствуйте, vadimcher, Вы писали:

V>Да, именно об этом. Просто в итоге ты использовал конкретные выражения для того, чтобы привести пример остатка (g(m)) при делении некоторой большой степени двойки (f(m)-1) на 10^m. Т.е., как я написал до этого, в твоем доказательстве не важно, действительно ли f() и g() выражают то, с чего ты начал. Т.е. для доказательства это не важно. Тем не менее, просто интересно.

B>>

B>>Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
B>>Количество возможных остатков равно f(k)
B>>Последний неповторяющийся остаток равен g(k)
B>>

1. Последний неповторяющийся остаток равен g(k) = 5*10^(k-1) + 2^(k-1)

Во-первых остатки повторяются (это очевидно и так).
Во-вторых g(k) действительно является остатком (это мы уже доказали).

Следуюший остаток после него будет 2*(5*10^(k-1) + 2^(k-1)) mod 10^k = 2^k
Минимальное n при котором остаток может быть равен 2^k равно k.
Также очевидно, что g(k) не является остатком при n < k.
Из этого следует, что минимальное n для остатка g(k) больше минимального n для остатка 2^k.

А это говорит о том, что для следующего n список остатков зациклится, а значит g(k) является последним неповторяющимся остатком.

2. Чему равно n, которое приводит к остатку g(k)?

Т.к. g() — остаток от деления 2^n на 10^k можем записать:
x*10^k + 5*10^(k-1) + 2^(k-1) = 2^n

Переносим 2^(k-1) и выносим общие множители
5*10^(k-1) * (2x+1) = 2^(k-1) * (2^(n-k+1) — 1)

Делим на 2^(k-1)
5^k (2x+1) = 2^(n-k+1) — 1

Т.е.
2^(n-k+1) === 1 (mod 5^k)

По теореме Эйлера:
a^ф(m) = 1 (mod m)
ф(5^k) = 4*5^(k-1)

Отсюда получаем:
a^(4*5^(k-1)) === 1 (mod 5^k), где a и 5^k взаимно простые

Возвращаясь к нашей степени двойки:
a^(4*5^(k-1)) = 2^(n-k+1)

Логарифмируем по основанию 2:
4*5^(k-1) * log a = n-k+1

Обозначим log a = s, откуда a = 2^s. Заметим также, что s>0 т.к. "a" не может быть 1 (не взаимно простое с 5^k)
n = s*4*5^(k-1) + k — 1, где s >= 1

Это формула n при котором получается остаток g()

3. Количество остатков f(k) = 4*5^(k-1) + k = 100*5^(k-3) + k

Теперь можно определить количество остатков от деления на 10^k
Возьмем минимальное n при котором получается последний неповторяющийся остаток g(k).
Тогда общее количество остатков будет равно n+1 (единицу прибавляем, т.к. степени начинаем считать с нуля)

В нашем случае минимальное n = 4*5^(k-1) + k — 1 (при s = 1)
Откуда f(k) = 4*5^(k-1) + k, ч.т.д.

P.S.Интересно, что остатки, стоящие самыми первыми в списке (т.е. для n < k) никогда не повторяются.
Например существует единственное число 2^n, которое при делении на 100 дает в остатке 2. Это само число 2 ,
т.е. числа вида 2^n никогда не заканчиваются на 02 и т.д.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher.
А>После нового года я постараюсь выложить и саму олимпиадную задачу и решение из сборника задач.

А>Заодно узнаем насколько она старая.

К сожалению, я так и не нашёл книги с решением задачи с помощью логарифмов.

Зато в книге "Зарубежные математические олимпиады" нашёл решение в стиле теоремы Эйлера:

[/img]http://files.rsdn.ru/41706/zad.jpg[/img]

[img]http://files.rsdn.ru/41706/solution.jpg[img]

PS Фотограф из меня не очень.

Здравствуйте, vadimcher, Вы писали:

По одному из вариантов программы (пусть не самый быстрый) на процессоре рейтинга 2000 считается 70 000 000 знаков в секунду.


число а17 — это приблизительно миллиардная степень двойки.

для расчета 2^1 000 000 000 придется обработать (1000000000 ^ 2) / (2 * 3.31) знаков. (3.31 — коэффициент ширины десятичного представления степени двойки)
итого это 151 057 401 812 688 821 знаков.
для их расчета 1-му процессору потребуется 2 157 962 883 секунд
или 599 434 часов
или 24 976 суток
или 68 лет

если на эту задачу бросить 70 процессоров, то потребуется почти год.

явно, что а17 расчитывалось, либо каким то другим способом (не удвоением), либо на каком то жутко мощном майнфрэйме
ну или на огромном количестве компов...

Здравствуйте, Аноним, Вы писали:

А>К сожалению, я так и не нашёл книги с решением задачи с помощью логарифмов.
Да его легко восстановить, вообще-то.

Пусть у нас есть An = 2**n;
Найдём число Q(n, k), представляющее k старших цифр An:

Это будет Q(n, k) = 2**n / 10**q(n), где q(n) = [log10( 2**n )] — k = [n log10( 2 )] — k.
(тут [х] обозначает "целая часть х")
Соотвественно, log10 Q(n, k) = log10( 2**n / 10**q(n) ) = n*log10( 2 ) — q(n) = n*log10( 2 ) + k — [n log10( 2 )]
То есть log10 Q(n, k) = k + { n log10( 2 ) }, где {x} -- это дробная часть x.

Довольно очевидно, что для любого иррационального x последовательность Bn = { n x } всюду плотна на [0, 1] (под "всюду плотна" я имею в виду, что в любой окрестности любой точки отрезка найдётся хотя бы одна точка из Bn)

Но это обозначает, что Q(n, k) принимает все значения на [10**k, 10**(k+1) — 1]...

E>Довольно очевидно, что для любого иррационального x последовательность Bn = { n x } всюду плотна на [0, 1] (под "всюду плотна" я имею в виду, что в любой окрестности любой точки отрезка найдётся хотя бы одна точка из Bn)

Если кому не очевидно, то вот док-во:

Рассмотрим наматывание на окружность радиуса 1/(2pi) угла в x радиан. По условию х иррационально, соответственно несоизмеримо с длинной нашей окружности, равной 1.
То есть если мы будем брать углы в Bn радиан, то ни при каких n != m не получится так, что точки Bn и Bm совпадут.
Соотвественно, мы всегда можем поставить на окружности столько разных точек, сколько нам надо.

Рассмотрим теперь диапазон углов длины 2a > 0. (скажем такой: [t0-a, t0+a]). Докажем, что в нём обязательно найдётся одна из точек Bn.

Лема 1. Найдутся два такие k < m, что расстояние от Bk до Bm на окружности будет меньше, чем 2a. Это очевидно, так как если мы возьмём первые [1 / a] + 1 точек, то где-то на окружности должно найтись две точки, на расстоянии меньшем чем 2a... Выберем ту из них, у которой меньший индекс за Bk, а ту, у которой больший за Bm.

Лема 2.
Очевидно, что длинна отрезка [Bn, Bn+k] зависит только от k, просто в силу осевой симметрии окружности

Лема 3.
Можно покрыть всю окружность точками, отстоящими друг от друга менее, чем на 2a.
Тоже очевидно. Берём пару точек из леммы 1, и с таким шагом покрываем постепенно всю окружность с шагом меньшем чем 2a

Ну, а из этого всего следует, что найдётся точка в диапазоне углов [t0-a, t0+a], для любого t0 и любого положительного a...

ЧТД.