026.cpp

Go to the documentation of this file.

using namespace std;
#include <iostream>
#include <vector>
#include "026_prime_table.h"

typedef unsigned long long verylong;

const verylong segment_max = 1e13;

const unsigned digits_per_segments = 13;


class bigNum
{
        vector<verylong> segments;
public:
        bigNum(unsigned);
        void times10plus9();
        unsigned mod(unsigned);
        unsigned digits();
        void print_all();
};

bigNum::bigNum(unsigned x)
{
        //assume x<max
        segments.push_back(x);
}

void bigNum::times10plus9()
{
        for (vector<verylong>::iterator p=segments.begin();p!=segments.end();p++)
                *p *= 10;
        segments.front() +=9;

        for (vector<verylong>::iterator p=segments.begin();p!=segments.end();p++) {
                unsigned count_out = *p / segment_max;

                if (count_out == 0) break;
                *p -= count_out * segment_max;

                if (p+1 == segments.end())
                        segments.push_back(count_out);
                else
                        *(p+1) += count_out;
        }
}

unsigned bigNum::mod(unsigned y)
{
        vector<verylong> seg2=segments;

        for (vector<verylong>::reverse_iterator p = seg2.rbegin()+1; p!=seg2.rend();p++) {
                unsigned count_out = *(p-1) % y;
                *p += count_out * segment_max;
                //print_all();
        }
        return *(seg2.begin()) % y;
}

unsigned bigNum::digits()
{
        unsigned no_of_segments = segments.size();
        unsigned digits_at_back = 0;
        for (unsigned k = segments.back();k>0;k/=10)
                digits_at_back++;

        return digits_at_back + digits_per_segments * (no_of_segments - 1);
}

void bigNum::print_all()
{
        for (vector<verylong>::reverse_iterator p=segments.rbegin();p!=segments.rend();p++)
                cout << *p;
        cout << endl;
}


using namespace std;
unsigned period(unsigned d)
{
        bigNum nines(9);

        while (nines.mod(d) != 0) {
                nines.times10plus9();
        }
        return nines.digits();
}

int main()
{
        prime_table primes;
        unsigned max_period = 0;
        unsigned max_d=0;

for (unsigned d = 7; d < 1000; d = primes.next(d)) 
{
                unsigned temp = period(d);
                if (temp > max_period) {
                        max_period = temp;
                        max_d = d;
                }
                
                cout << d << '\t' << temp << endl;
        }
        cout << max_d << '\t' << max_period << endl;
        return 0;
}