Ты настолько не любишь STL?

E>

E>static void expand10times( small* buffer, int count )
E>{
E>    const small* src = buffer + 1;
E>    small* dst = buffer + 1 + count;
E>    for( int i = count * 9; i > 0; --i )
E>        *dst++ = *src++;
E>    ++*--dst;

std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count);
++buffer[10 * count];

E>}
E>static void fillLeft( small* dst, int start, small init_to )
E>{
E>    small* from = dst + start;
E>    small* to = dst + start * 10;
E>    while( from != to )
E>        *from++ = init_to;
E>}

std::fill(dst + start, dst + start * 10, init_to);

E>a(9) за пять минут

Мой результат похуже, выкладывать не стану. Я решил использовать 10¹⁶-ричную систему счисления, но из того ничего дельного не вышло.

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

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

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

S>>>Здравствуйте, 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).

S>>>Обратная задача

S>>>Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !!
S>>>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?

V>>Не существует. Если мы докажем (теоретически), что a(k) есть для любого k, то последовательность таких чисел уходит в бесконечность.

S>Почему?
S>Чем длинее числа, тем вероятность того что встретится два нуля подрад — увеличивается, следовательно когда то наступит момент что эта вероятность будет равна 1

Я твой второй вопрос не так понял.

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

RO>Ты настолько не любишь STL?
Даже ещё больлше, в отличии от функций memcpy и memset

Просто сначала этот код на другой библиотеке был. Потом я её отковырял...

RO>std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count);
RO>++buffer[10 * count];

А разве так можно?


E>>a(9) за пять минут

RO>Мой результат похуже, выкладывать не стану. Я решил использовать 10¹⁶-ричную систему счисления, но из того ничего дельного не вышло.
Зато он, наверное, на хорошем STL
Выкладывай, не стесняйся.
Я сейчас опубликую более вменяемый вариант...

E>9 -- меньше минуты. Написал из головы, вроде сразу заработало...

Вот, теперь попробовал несколько вариантов. Как и следовало ожидать самый быстрый работает 4-ками цифр.
Пробовал на Core(TM) Duo CPU T2450 2,00 GHz, да ещё и под вистой

Итого:
Вариант с цифрой на байт:

0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:32 : 2^100823 = 9, 9, len = 30351

#include "stdafx.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>

const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
    
const int digits_count = 4;
const int max_dig_value = 9999;

typedef signed char small_num;

int my_max( int i1, int i2 ) { return i1 > i2 ? i1 : i2; }

static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
    char buffer[1024];
    assert( seconds >= 0 );
    sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
    return buffer;
}

class CDigitsParser {
public:
    CDigitsParser( int num_, int max_dig_count = digits_count ) : 
                num( num_ ), dig_count( -1 ), left_count( max_dig_count ) 
    {
        assert( max_dig_count > 0 && num != 0 );
        shift_one_dig();
        assert( !is_processed() );
        
        right_count = shift_right_z();
        max_in_count = 0;
        shift_right_nz();
        while( num != 0 ) {
            const int in_count = shift_right_z();
            max_in_count = my_max( max_in_count, in_count );
            shift_right_nz();
        }
        assert( dig_count > 0 && dig_count <= left_count );
        left_count -= dig_count;
        assert( is_processed() );
    }
    int GetLeftCount() const { assert( is_processed()); return left_count; }
    int GetInCount() const { assert( is_processed()); return max_in_count; }
    int GetRightCount() const { assert( is_processed()); return right_count; }
    
private:
    enum { base = 10 };
    
    int num;
    int dig;
    int dig_count;
    int left_count;
    int max_in_count;
    int right_count;

    bool is_processed() const { return num == 0 && dig == 0; }
    void shift_one_dig()    
    {
        dig = num % base;
        num /= base;
        dig_count++;
    }
    int shift_right_z()
    {
        assert( !is_processed() );
        int count = 0;
        while( dig == 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
    
    int shift_right_nz()
    {
        int count = 0;
        while( dig != 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
};    //    CDigitsParser


small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };

void init_tables()
{
    for( int i = 1; i <= max_dig_value; ++i ) {
        CDigitsParser p( i );
        left_z_count[i] = p.GetLeftCount();
        in_z_count[i] = p.GetInCount();
        right_z_count[i] = p.GetRightCount();
    }
}


const unsigned char lowDigit[] = { 0, 2, 4, 6, 8, 0, 2, 4, 6, 8 };
const unsigned char hiDigit[] =  { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 };


class PowerOf2VeryLongNumber {
    typedef std::vector<unsigned char> TDigits;
    TDigits digits;
public:
    PowerOf2VeryLongNumber() { digits.push_back( 1 ); }

    int Mult2AndRetMax0Count()
    {
        int zerCount = 0;
        int bestZerCount = 0;
        if( digits[digits.size() - 1] != 0 )
            digits.push_back( 0 );
        int carry = 0;
        for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
            const unsigned char curDig = lowDigit[*i] + carry;
            carry = hiDigit[*i];
            *i = curDig;
            if( curDig == 0 ) {
                ++zerCount;
                if( zerCount > bestZerCount && (i+1)!=digits.end() ) {
                    bestZerCount = zerCount;
                }
            } else {
                zerCount = 0;
            }
        }
        assert( carry == 0 );
        return bestZerCount;
    }
    template<typename TStream>
    TStream& Output( TStream& dst ) const 
    {
        for( TDigits::const_reverse_iterator i = digits.rbegin(); i != digits.rend(); ++i ) {
            dst << (int)*i;
        }
        return dst;
    }

    int Length() const { return digits.size() - ( digits[digits.size() - 1] == 0 ); }

};

template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
    return x.Output( dst );
}

struct Result {
    int PowerValue;
    PowerOf2VeryLongNumber x;
};

int _tmain(int argc, _TCHAR* argv[])
{
    //init_tables();    
    ///std::cout << time_report() << std::endl;    
    PowerOf2VeryLongNumber x;
    std::vector<Result> result;
    Result tmp = { 0 };
    result.push_back( tmp );
    for( int i = 1; i < tryTo; i++ ) {
        int zCount = x.Mult2AndRetMax0Count();
        if( ( i % logPeriod ) == 0 ) {
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/* << ", " << x */<< " <-\r";
        }
        
        while( result.size() <= zCount ) {
            Result r = { i, x };
            result.push_back( r );
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/* << ", " << x */<< "   " << std::endl;
        }
    }
    std::cout << "--------------------------" << std::endl;
    for( int i = 1; i < result.size(); i++ ) {
        std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length() 
            /*<< " = " << result[i].x */<< std::endl;
    }

    return 0;
}

Вариант с двумя цифрами на байт:

0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:18 : 2^100823 = 9, 9, len = 30351

#include "stdafx.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>

const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
    
typedef signed char small_num;

const int digits_count = 2;
const int max_dig_value = 99;
typedef small_num TAllDigitsNum; 


void set_if_g( int& dst, int src )
{
    if( dst < src )
        dst = src;
}

static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
    char buffer[1024];
    assert( seconds >= 0 );
    sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
    return buffer;
}

class CDigitsParser {
public:
    CDigitsParser( int num_, int max_dig_count = digits_count ) : 
                num( num_ ), dig_count( -1 ), left_count( max_dig_count ) 
    {
        assert( max_dig_count > 0 && num != 0 );
        shift_one_dig();
        assert( !is_processed() );
        
        right_count = shift_right_z();
        max_in_count = 0;
        shift_right_nz();
        while( num != 0 ) {
            const int in_count = shift_right_z();
            set_if_g( max_in_count, in_count );
            shift_right_nz();
        }
        assert( dig_count > 0 && dig_count <= left_count );
        left_count -= dig_count;
        assert( is_processed() );
    }
    int GetLeftCount() const { assert( is_processed()); return left_count; }
    int GetInCount() const { assert( is_processed()); return max_in_count; }
    int GetRightCount() const { assert( is_processed()); return right_count; }
    
private:
    enum { base = 10 };
    
    int num;
    int dig;
    int dig_count;
    int left_count;
    int max_in_count;
    int right_count;

    bool is_processed() const { return num == 0 && dig == 0; }
    void shift_one_dig()    
    {
        dig = num % base;
        num /= base;
        dig_count++;
    }
    int shift_right_z()
    {
        assert( !is_processed() );
        int count = 0;
        while( dig == 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
    
    int shift_right_nz()
    {
        int count = 0;
        while( dig != 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
};    //    CDigitsParser


small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };

void init_tables()
{
    for( int i = 1; i <= max_dig_value; ++i ) {
        CDigitsParser p( i );
        left_z_count[i] = p.GetLeftCount();
        in_z_count[i] = p.GetInCount();
        right_z_count[i] = p.GetRightCount();
    }
}


class PowerOf2VeryLongNumber {
    typedef TAllDigitsNum TDig;        
    typedef std::vector<TDig> TDigits;
    TDigits digits;
public:
    PowerOf2VeryLongNumber() { digits.push_back( 1 ); }

    int Mult2AndRetMax0Count()
    {
        int cur_z_count = 0;
        int best_z_count = 0;
        int carry = 0;
        for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
            int dig = *i*2 + carry;
            if( dig > max_dig_value ) {
                carry = 1;
                dig -= max_dig_value + 1;
            } else {
                carry = 0;
            }
            *i = dig;
            if( dig == 0 ) {
                cur_z_count += digits_count;
            } else {
                set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
                //set_if_g( best_z_count, in_z_count[dig] );    //    для больших чисел не важно...
                cur_z_count = left_z_count[dig];
            }
        }
        if( carry != 0 ) {
            digits.push_back( carry );
        }
        return best_z_count;
    }
    
    template<typename TStream>
    TStream& Output( TStream& dst ) const 
    {
        TDigits::const_reverse_iterator i = digits.rbegin();    
        dst << (int)*i;
        for( ++i; i != digits.rend(); ++i ) {
            dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
        }
        return dst;
    }

    int Length() const 
    { 
        assert( digits[digits.size() - 1] != 0 );
        return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]]; 
    }

};

template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
    return x.Output( dst );
}

struct Result {
    int PowerValue;
    PowerOf2VeryLongNumber x;
};

int _tmain(int argc, _TCHAR* argv[])
{
    init_tables();    

    PowerOf2VeryLongNumber x;
    std::vector<Result> result;
    Result tmp = { 0 };
    result.push_back( tmp );
    for( int i = 1; i < tryTo; i++ ) {
        int zCount = x.Mult2AndRetMax0Count();
        if( ( i % logPeriod ) == 0 ) {
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/* << ", " << x */<< " <-\r";
        }
        
        while( result.size() <= zCount ) {
            Result r = { i, x };
            result.push_back( r );
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/** << ", " << x **/<< "   " << std::endl;
        }
    }
    std::cout << "--------------------------" << std::endl;
    for( int i = 1; i < result.size(); i++ ) {
        std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length() 
            /*<< " = " << result[i].x */<< std::endl;
    }

    return 0;
}

Вариант с четырьмя цифрами на short:

0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:10 : 2^100823 = 9, 9, len = 30351

#include "stdafx.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>

const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
    
typedef signed char small_num;

const int digits_count = 4;
const int max_dig_value = 9999;
typedef short TAllDigitsNum; 


void set_if_g( int& dst, int src )
{
    if( dst < src )
        dst = src;
}

static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
    char buffer[1024];
    assert( seconds >= 0 );
    sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
    return buffer;
}

class CDigitsParser {
public:
    CDigitsParser( int num_, int max_dig_count = digits_count ) : 
                num( num_ ), dig_count( -1 ), left_count( max_dig_count ) 
    {
        assert( max_dig_count > 0 && num != 0 );
        shift_one_dig();
        assert( !is_processed() );
        
        right_count = shift_right_z();
        max_in_count = 0;
        shift_right_nz();
        while( num != 0 ) {
            const int in_count = shift_right_z();
            set_if_g( max_in_count, in_count );
            shift_right_nz();
        }
        assert( dig_count > 0 && dig_count <= left_count );
        left_count -= dig_count;
        assert( is_processed() );
    }
    int GetLeftCount() const { assert( is_processed()); return left_count; }
    int GetInCount() const { assert( is_processed()); return max_in_count; }
    int GetRightCount() const { assert( is_processed()); return right_count; }
    
private:
    enum { base = 10 };
    
    int num;
    int dig;
    int dig_count;
    int left_count;
    int max_in_count;
    int right_count;

    bool is_processed() const { return num == 0 && dig == 0; }
    void shift_one_dig()    
    {
        dig = num % base;
        num /= base;
        dig_count++;
    }
    int shift_right_z()
    {
        assert( !is_processed() );
        int count = 0;
        while( dig == 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
    
    int shift_right_nz()
    {
        int count = 0;
        while( dig != 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
};    //    CDigitsParser


small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };

void init_tables()
{
    for( int i = 1; i <= max_dig_value; ++i ) {
        CDigitsParser p( i );
        left_z_count[i] = p.GetLeftCount();
        in_z_count[i] = p.GetInCount();
        right_z_count[i] = p.GetRightCount();
    }
}


class PowerOf2VeryLongNumber {
    typedef TAllDigitsNum TDig;        
    typedef std::vector<TDig> TDigits;
    TDigits digits;
public:
    PowerOf2VeryLongNumber() { digits.push_back( 1 ); }

    int Mult2AndRetMax0Count()
    {
        int cur_z_count = 0;
        int best_z_count = 0;
        int carry = 0;
        for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
            int dig = *i*2 + carry;
            if( dig > max_dig_value ) {
                carry = 1;
                dig -= max_dig_value + 1;
            } else {
                carry = 0;
            }
            *i = dig;
            if( dig == 0 ) {
                cur_z_count += digits_count;
            } else {
                set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
                set_if_g( best_z_count, in_z_count[dig] );    //    для больших чисел не важно...
                cur_z_count = left_z_count[dig];
            }
        }
        if( carry != 0 ) {
            digits.push_back( carry );
        }
        return best_z_count;
    }
    
    template<typename TStream>
    TStream& Output( TStream& dst ) const 
    {
        TDigits::const_reverse_iterator i = digits.rbegin();    
        dst << (int)*i;
        for( ++i; i != digits.rend(); ++i ) {
            dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
        }
        return dst;
    }

    int Length() const 
    { 
        assert( digits[digits.size() - 1] != 0 );
        return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]]; 
    }

};

template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
    return x.Output( dst );
}

struct Result {
    int PowerValue;
    PowerOf2VeryLongNumber x;
};

int _tmain(int argc, _TCHAR* argv[])
{
    init_tables();    

    PowerOf2VeryLongNumber x;
    std::vector<Result> result;
    Result tmp = { 0 };
    result.push_back( tmp );
    for( int i = 1; i < tryTo; i++ ) {
        int zCount = x.Mult2AndRetMax0Count();
        if( ( i % logPeriod ) == 0 ) {
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/* << ", " << x */<< " <-\r";
        }
        
        while( result.size() <= zCount ) {
            Result r = { i, x };
            result.push_back( r );
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/** << ", " << x **/<< "   " << std::endl;
        }
    }
    std::cout << "--------------------------" << std::endl;
    for( int i = 1; i < result.size(); i++ ) {
        std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length() 
            /*<< " = " << result[i].x */<< std::endl;
    }

    return 0;
}

Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)

0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:09 : 2^100823 = 9, 9, len = 30351

#include "stdafx.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>

const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
    
typedef signed char small_num;

const int digits_count = 4;
const int max_dig_value = 9999;
typedef short TAllDigitsNum; 


void set_if_g( int& dst, int src )
{
    if( dst < src )
        dst = src;
}

static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
    char buffer[1024];
    assert( seconds >= 0 );
    sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
    return buffer;
}

class CDigitsParser {
public:
    CDigitsParser( int num_, int max_dig_count = digits_count ) : 
                num( num_ ), dig_count( -1 ), left_count( max_dig_count ) 
    {
        assert( max_dig_count > 0 && num != 0 );
        shift_one_dig();
        assert( !is_processed() );
        
        right_count = shift_right_z();
        max_in_count = 0;
        shift_right_nz();
        while( num != 0 ) {
            const int in_count = shift_right_z();
            set_if_g( max_in_count, in_count );
            shift_right_nz();
        }
        assert( dig_count > 0 && dig_count <= left_count );
        left_count -= dig_count;
        assert( is_processed() );
    }
    int GetLeftCount() const { assert( is_processed()); return left_count; }
    int GetInCount() const { assert( is_processed()); return max_in_count; }
    int GetRightCount() const { assert( is_processed()); return right_count; }
    
private:
    enum { base = 10 };
    
    int num;
    int dig;
    int dig_count;
    int left_count;
    int max_in_count;
    int right_count;

    bool is_processed() const { return num == 0 && dig == 0; }
    void shift_one_dig()    
    {
        dig = num % base;
        num /= base;
        dig_count++;
    }
    int shift_right_z()
    {
        assert( !is_processed() );
        int count = 0;
        while( dig == 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
    
    int shift_right_nz()
    {
        int count = 0;
        while( dig != 0 ) {
            shift_one_dig();
            count++;
        }
        return count;
    }
};    //    CDigitsParser


small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };

void init_tables()
{
    for( int i = 1; i <= max_dig_value; ++i ) {
        CDigitsParser p( i );
        left_z_count[i] = p.GetLeftCount();
        in_z_count[i] = p.GetInCount();
        right_z_count[i] = p.GetRightCount();
    }
}


class PowerOf2VeryLongNumber {
    typedef TAllDigitsNum TDig;        
    typedef std::vector<TDig> TDigits;
    TDigits digits;
public:
    PowerOf2VeryLongNumber() { digits.push_back( 1 ); }

    int Mult2AndRetMax0Count()
    {
        int cur_z_count = 0;
        int best_z_count = 0;
        int carry = 0;
        for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
            int dig = *i*2 + carry;
            if( dig > max_dig_value ) {
                carry = 1;
                dig -= max_dig_value + 1;
            } else {
                carry = 0;
            }
            *i = dig;
            if( dig == 0 ) {
                cur_z_count += digits_count;
            } else {
                set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
                //set_if_g( best_z_count, in_z_count[dig] );    //    для больших чисел не важно...
                cur_z_count = left_z_count[dig];
            }
        }
        if( carry != 0 ) {
            digits.push_back( carry );
        }
        return best_z_count;
    }
    
    template<typename TStream>
    TStream& Output( TStream& dst ) const 
    {
        TDigits::const_reverse_iterator i = digits.rbegin();    
        dst << (int)*i;
        for( ++i; i != digits.rend(); ++i ) {
            dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
        }
        return dst;
    }

    int Length() const 
    { 
        assert( digits[digits.size() - 1] != 0 );
        return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]]; 
    }

};

template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
    return x.Output( dst );
}

struct Result {
    int PowerValue;
    PowerOf2VeryLongNumber x;
};

int _tmain(int argc, _TCHAR* argv[])
{
    init_tables();    

    PowerOf2VeryLongNumber x;
    std::vector<Result> result;
    Result tmp = { 0 };
    result.push_back( tmp );
    for( int i = 1; i < tryTo; i++ ) {
        int zCount = x.Mult2AndRetMax0Count();
        if( ( i % logPeriod ) == 0 ) {
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/* << ", " << x */<< " <-\r";
        }
        
        while( result.size() <= zCount ) {
            Result r = { i, x };
            result.push_back( r );
            std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1 
                << ", len = " << x.Length()/** << ", " << x **/<< "   " << std::endl;
        }
    }
    std::cout << "--------------------------" << std::endl;
    for( int i = 1; i < result.size(); i++ ) {
        std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length() 
            /*<< " = " << result[i].x */<< std::endl;
    }

    return 0;
}

Будет время -- попробую обработать переполнение кэша.
Идея такая, что как только массив "цифр" перестаёт помещаться в кэш, так сразу и приходят тормоза.
Если отказаться от хранения самих степеней двойки, для каждого k, то можно сделать хитро.
Фактически Mult2AndRetMax0Count() идёт по массиву "цифр" и меняет его, накапливая некоторое состояние (перенос, длина максимальной обнаруженной цепочки 0, длина текущей обнаруженной цепочки 0, позиция). Можно проходить по куску массива "цифр", который помещается в кэш, и накапливать массив состояний, полученных на границе куска после первого прохода, после второго и т. д. Пока кэш не закончится.
Потом можно переходить к обработке след. куска массива "цифр" и т. д. А когда дойдём до конца массива "цифр" -- узнаем несколько a(k), если повезёт...

Хотя конечно, для радикального ускорения всё этой сосиски её надо на "КУДУ" перенести. Типа массивы *_z_count затолкать в текстурную память, хранить пары "цифр" и переносов, и потом прогонять логарифмическим суммированием по всей этой штуке. Должно быть очень сильно быстрее. Раз в 1000 на хорошей карточке, наверное...

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

S>>>а(8) — до 2х секунд!
S>>>а(9) — 80 секунд!

S>>а(10) — 2^559940 — 24 минуты и 20 секунд

S>а(11) — 2^1148303 — 47 минут и 16 секунд

0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:09 : 2^100823 = 9, 9, len = 30351
0:04:24 : 2^559940 = 10, 10, len = 168559
0:18:23 : 2^1148303 = 11, 11, len = 345674

Гонял на Core(TM) Duo CPU T2450 2,00 GHz под вистой...
А ты?

Здравствуйте, 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).

Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
Может кто-то глубже и написал, все читать не стал — долго.

отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?

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

S>Здравствуйте, 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).

S>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
S>Может кто-то глубже и написал, все читать не стал — долго.

S>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?

Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?

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

S>отрицательные -- n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
Прикольно, но скучно. ВО всяком случае, в качестве этюда для программистов

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

V>Все верно расчитали. Тут можно посмотреть вплоть до a(17): здесь. Внизу комментарий: некто Sacha Roscoe добавил a(15), затем через пару недель a(16), а затем еще a(17)... через 4 года.

... а потом он защитил докторскую диссертацию в своём Западно-Австралийском Университете и забил.

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

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

S>>Здравствуйте, 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).

S>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
S>>Может кто-то глубже и написал, все читать не стал — долго.

S>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?

V>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
Нигде не сказано => не понятно. А главное, что в первой строчке нету минимуальности И если бы мне дали только первую стоку, то точно не понятно....

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

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

S>>Здравствуйте, 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).

S>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
S>>Может кто-то глубже и написал, все читать не стал — долго.

S>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?

V>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
образование: математик, системный программист

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

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

S>>отрицательные -- n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
E>Прикольно, но скучно. ВО всяком случае, в качестве этюда для программистов
Каков вопрос, таков ответ. Задачу поставили, я написал решение

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

S>Каков вопрос, таков ответ. Задачу поставили, я написал решение

Ой ли?

Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
Может кто-то глубже и написал, все читать не стал — долго.

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

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

Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило!
Ради интереса написал на Лиспе (DrScheme):

#lang scheme
(require srfi/40/stream)

;Поток степеней двойки. Состоит из пар: степень, показатель степени.
(define (double-stream-from n k)
  (stream-cons (cons n k)
               (double-stream-from (* 2 n) (+ k 1))))

(define pow2-stream (double-stream-from 1 0))

;Функция проверки количества нулей подряд в десятичной системе.
(define (check n k)
  (define (check-iter n k z)
    (if (= n 0)
        false
        (if (= k z)
            true
            (if (= (remainder n 10) 0)
                (check-iter (quotient n 10) k (+ z 1))
                (check-iter (quotient n 10) k 0)))))
  (check-iter n k 0))

;Поток отфильтрованных степеней двойки.
(define (filtered-pow2-stream-from n s)
  (if (check (car (stream-car s)) n)
      (stream-cons (stream-car s)
                   (filtered-pow2-stream-from (+ n 1) (stream-cdr s)))
      (filtered-pow2-stream-from n (stream-cdr s))))

(define filtered-pow2-stream (filtered-pow2-stream-from 1 pow2-stream))

;Отображение потока.
(define (display-pow2-stream s)
  (stream-for-each display-pow s))

(define (display-pow x)
  (newline)
  (display (cdr x)))

(define display-filtered-pow2-stream (display-pow2-stream filtered-pow2-stream))

Работает очень медленно. Зато функционально И что интересно, сам распараллелился на два потока — один строит степени двойки, а другой эти степени фильрует.
Лисп изучаю, если кто покритикует, буду рад.

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

А>Решение на Haskell.
А>

А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>

Неужели еще никто не написал решение на J или K?

А вот моя версия. Подход немножко другой, используется 10¹⁶-ричная система счисления.

#include <vector>
#include <iostream>
#include <fstream>
#include <cassert>
#include <boost/lexical_cast.hpp>

using std::size_t;

typedef unsigned long long digit;
typedef std::vector<digit> bigint;

size_t const LOG_BASE = 16;
digit const power10[17] = {
    (digit)1ULL,
    (digit)10ULL,
    (digit)100ULL,
    (digit)1000ULL,
    (digit)10000ULL,
    (digit)100000ULL,
    (digit)1000000ULL,
    (digit)10000000ULL,
    (digit)100000000ULL,
    (digit)1000000000ULL,
    (digit)10000000000ULL,
    (digit)100000000000ULL,
    (digit)1000000000000ULL,
    (digit)10000000000000ULL,
    (digit)100000000000000ULL,
    (digit)1000000000000000ULL,
    (digit)10000000000000000ULL,
};
digit const BASE = power10[LOG_BASE];

bool has_k_zeros(digit const d, size_t const k, size_t& leftover)
{
    if(leftover >= k)
    {
        return true;
    }
    if(leftover > 0 && d % power10[k - leftover] == 0)
    {
        return true;
    }

    digit const factor_positive = power10[k];
    digit const factor_possible = power10[k / 2];

    for(digit i = d; i; i /= factor_possible)
    {
        if(i % factor_possible == 0)
        {
            leftover = LOG_BASE;
            for(digit j = d; j; )
            {
                if(j % factor_positive == 0)
                {
                    return true;
                }

                while(j % 10 == 0)
                {
                    j /= 10;
                    --leftover;
                }
                j /= 10;
                --leftover;
            }
            return false;
        }
    }

    leftover = LOG_BASE;
    for(size_t i = 0; i < LOG_BASE; ++i)
    {
        if(d >= power10[LOG_BASE - i - 1])
        {
            leftover = i;
            break;
        }
    }
    return false;
}

bigint& mul2(bigint& n)
{
    digit carry = 0;
    for(size_t i = 0; i < n.size(); ++i)
    {
        n[i] *= 2;
        n[i] += carry;
        if(n[i] >= BASE)
        {
            carry = n[i] / BASE;
            n[i] %= BASE;
        }
        else
        {
            carry = 0;
        }
    }
    if(carry > 0)
    {
        n.push_back(carry);
    }
    return n;
}

int main(int argc, char** argv)
{
    assert(argc == 2);
    size_t const k = boost::lexical_cast<size_t>(argv[1]);

    size_t p = 0;
    bigint n;
    n.reserve(10240);
    n.push_back(1);

    std::ofstream tty("/dev/tty");

    while(1)
    {
        {
            size_t leftover = 0;
            for(size_t i = 0; i < n.size(); ++i)
            {
                if(has_k_zeros(n[i], k, leftover))
                {
                    std::cout << p << std::endl;
                    return 0;
                }
            }
        }

        mul2(n);

        ++p;

        if(p % 10000 == 0)
        {
            tty << p << "..." << std::endl;
        }
    }
}

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

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

S>>>>а(8) — до 2х секунд!
S>>>>а(9) — 80 секунд!

S>>>а(10) — 2^559940 — 24 минуты и 20 секунд

S>>а(11) — 2^1148303 — 47 минут и 16 секунд

E>

0:00:01 : 2^242 = 3, 3, len = 73
E>0:00:01 : 2^377 = 4, 4, len = 114
E>0:00:01 : 2^1491 = 5, 5, len = 449
E>0:00:01 : 2^1492 = 6, 6, len = 450
E>0:00:01 : 2^6801 = 7, 7, len = 2048
E>0:00:01 : 2^14007 = 8, 8, len = 4217
E>0:00:09 : 2^100823 = 9, 9, len = 30351
E>0:04:24 : 2^559940 = 10, 10, len = 168559
E>0:18:23 : 2^1148303 = 11, 11, len = 345674

Гонял на Core(TM) Duo CPU T2450 2,00 GHz под вистой...
E>А ты?

Семпрон 1.8 W2003 в belownormal

a(12) — 2^4036332 11 часов 18 минут

сейчас приближается к 10 миллионам со скоростью гдето 20 чисел в секунду

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

E>Вариант с двумя цифрами на байт:
E>Вариант с четырьмя цифрами на short:
E>Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)

А как на счет 8 на INT?

... а еще есть вариант 4 цифры на ИНТ, (по 1 на байт)

E>Будет время -- попробую обработать переполнение кэша.

Есть более радикальное решение:
Обрабатывать числа по частям. Ведь для удвоения нам достаточно знать цифру с которой начинать, а это всегда 1, и значение переноса из предыдущего разряда, это 1 или 0 — его запоминать в файле.

Расчитываем числа, длиной например в 1 000 000, — это приблизительно 3 200 000-я степень двойки. Продолжаем считать их например до 1000 000 000 000, запоминая в файле для каждой степени один байт, в котором 1 бит — значение переноса, остальные биты — количество нулей, которые имело число с левой стороны. Таким образом получаем файл в 1000 000 байт.

Затем мы расчитываем числа со степени 3 200 000, начиная с 1, учитывая значения переноса из файла. А при подсчете нулей, начальное количество нулей берем так же из файла.

Ресурс файла по количеству нулей — 127. То есть эта схема файла позволит рассчитать числа до 127 нулей подряд.

Этот алгоритм позволит избавить поиск чисел от зависимости на количество используемой памяти программой. И кстати легко может быть распределен между компьютерами.
1-й ищет части числа 1 000 000 000 000? второй 1 000 000 000 000, третий 1 000 000 000 000, четвертый 1 000 000 000 000.

Кто возьмется писать такую программу, просьба маленькая :
— сделать консольную программу, которая в качестве параметров принимает количество итераций, выходной файл переносов, входной файл переносов. (2 параметра — считать что перенос всегда 0)
— программа должна делать периодическое сохранение промежуточных данных (всего массива чисел), для того чтобы в любой момент можно было продолжить вычисления.
— должна позволить продолжить вычисления, получив четвертый параметр — текущее состояние



Удачи, программисты!

Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Seon, Вы писали:
S>>Последнее число, в котором нет двух нулей подряд — 2^2114 !
E>Два вопроса.
E>1) Какие есть ваши доказательства?
программа обработала числа до 2^10 000 000. Вероятность появления 2х нулей подряд падала очень быстро.
Вероятность встретить 2 нуля подряд в числах такого размера вероятна равна 0.
E>2) "2114!" -- это факториал?
Нет, просто 2^2114

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

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

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

S>>>Здравствуйте, 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).

S>>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
S>>>Может кто-то глубже и написал, все читать не стал — долго.

S>>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?

V>>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
S>Нигде не сказано => не понятно. А главное, что в первой строчке нету минимуальности И если бы мне дали только первую стоку, то точно не понятно....

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