Efficient solution to a problem?

[Krofna]

This problem was on yesterdays Croatian Open Competition in Informatics:

Let us begin with a positive integer N and find the smallest positive integer which doesn't divide N.
If we repeat the procedure with the resulting number, then again with the new result and so on, we will
eventually obtain the number 2 (two). Let us define strength(N) as the length of the resulting
sequence.
For example, for N = 6 we obtain the sequence 6, 4, 3, 2 which consists of 4 numbers, thus strength(6) = 4.
Given two positive integers A < B, calculate the sum of strengths of all integers between A and B
(inclusive), that is,
strength(A) + strength(A + 1) + ... + strength(B).

My solution:

#include <iostream>
#include <cstdint>

uint32_t snaga(uint32_t A, uint32_t& s)
{
    if(A == 2)
    {
        ++s;
        return s;
    }
    else if(A == 3)
    {
        ++s;
        return snaga(2, s);
    }

    if(A % 2 == 0)
    {
        for(int i = 3; ; ++i)
        {
            if(A % i != 0)
            {
                ++s;
                return snaga(i, s);
            }
        }
    }

    ++s;
    return snaga(2, s);
}

int main()
{
    uint32_t A, B;
    uint64_t C = 0;
    std::cin >> A >> B;

    for(uint32_t i = A; i <= B; ++i)
    {
        uint32_t s = 0;
        C += (uint64_t)snaga(i, s);
    }

    std::cout << C;
    return 0;
}

Sample I/O:

input: 3 6
output:11

input: 100 200
output: 262

It turned out to either wrong on some input or slow(1 sec time limit on a crap machine). What did I do wrong here?

[helios]

I can't find anything wrong with your code, besides the possibility of a stack overflow. I would have written it like this:

uint32_t snaga(uint32_t n){
	for (uint32_t s=0;;){
		s++;
		if (n == 2)
			return s;
		for (int i = 2; ; ++i){
			if(n % i != 0){
				n=i;
				break;
			}
		}
	}
}

//...

//if B=2^32-1, the condition i<=B will always be true.
for(uint32_t i = A; i < B; ++i){
	C += (uint64_t)snaga(i);
}
C += (uint64_t)snaga(B);

[ne555]

>slow(1 sec time limit on a crap machine)
Your algorithm is O(n), ¿how big is B-A? You need to make it O(1)
Supposing N<2^32, the maximum `smallest positive integer which doesn't divide N' is less than 30 (¿how did I obtain that?)

Instead of a linear walk, work with the extremes. Given a number N, ¿how many numbers n<=N are not divisible by 2? Their strength will be 2

Now consider the numbers that are divisible by 2, ¿how many are not by 3? That's easy, two thirds.
...
The numbers that are divisible by 2, 3, 4, 5, 6 but not by 7: six sevenths
(be careful with modulus)
(I'll let you figure out the composite numbers)

Compute the strength of the numbers from 2 to 30. Store in an array.

for( int K=2; K<30; ++K)
   total += how_many(N, K) * (strength[K]+1);

how_many counts n<=N | mod(n,b)== 0, b<K and mod(n,K)!=0

Be careful to not recount the numbers from 2 to 30

[helios]

It's not as simple as that, ne555.
According to you, how many integers between 1 and 100 are divisible by 2 and not 3? And by 2 and 3 but not 4?

[ne555]

Because 3 is prime, for the number to be a multiple of 3 it must be of the way n=3k
We have numbers of the form k=2j so that means n=3*2*j -> j = floor( n/(3*2) )

Those are the divisible by 2 that are also divisible by 3. But you want n/2 - j In your example 50-16 = 34

In the case of a composite, you've got 4 that's 2*2 and we got numbers that are n=2*3*k, so we need that k=2j -> j=n/(2*2*3)
In the example 16 - 8 = 8, namely: 6, 18, 30, 42, 54, 66, 78, 90.

So as general rule how_many(N,K) = N/mcm(1..K-1) - N/mcm(1..K)

Edit: Sorry, I think you know the mcm as LCM (least common multiple)

> Be careful to not recount the numbers from 2 to 30
Well, that can't happen. The number can't be in its strength set.

[tntxtnt]

my solution for 3 <= A < B < 10^17
sumStrength_f (a, b)
sumStrength (a, b) is for checking sumStrength_f()

#include <iostream>
using namespace std;

const __int64 TIER1 = 6; //lcm up to prime < 4
const __int64 TIER2 = 420; //lcm up to prime < 8
const __int64 TIER3 = 360360; //lcm up to prime < 16
const __int64 TIER4 = 72201776446800; //lcm up to prime < 32

__int64 strengthUpto(__int64 n)
{
    __int64 even = n/2;  //too lazy to exclude 2
    __int64 odd  = n - even; //too lazy to exclude 1

    __int64 tier1 = n/TIER1;
    __int64 tier2 = n/TIER2;
    __int64 tier3 = n/TIER3;
    __int64 tier4 = n/TIER4;

    tier1 = tier1 - tier1/2;
    tier2 = tier2 - tier2/2;
    tier3 = tier3 - tier3/2;
    tier4 = tier4 - tier4/2;

    return odd*2 + even*3 + (tier1+tier2+tier3+tier4);
}

__int64 strength(__int64 n)
{
    if (n%2 == 0)
    {
        for (int i = 3; i < n; ++i)
            if (n%i != 0)
                return 1 + strength(i);
    }
    return 2;
}

__int64 sumStrength(__int64 a, __int64 b)
{
    __int64 sum = 0;
    for (__int64 n = a; n <= b; ++n)
        sum += strength(n);
    return sum;
}

__int64 sumStrength_f(__int64 a, __int64 b)
{
    return strengthUpto(b) - strengthUpto(a-1);
}

int main()
{
    cout << sumStrength  (3,6) << endl;
    cout << sumStrength_f(3,6) << endl << endl;
    
    cout << sumStrength  (100,200) << endl;
    cout << sumStrength_f(100,200) << endl << endl;
    
    cout << sumStrength  (100,1000) << endl;
    cout << sumStrength_f(100,1000) << endl << endl;

    cout << sumStrength  (3,20000000) << endl; //about 3s
    cout << sumStrength_f(3,20000000) << endl << endl;
    
    cout << sumStrength  (72201775446800,72201777446800) << endl;
    cout << sumStrength_f(72201775446800,72201777446800) << endl << endl;

  //cout << sumStrength  (3,1172201777446800) << endl; //never finish...
    cout << sumStrength_f(3,1172201777446800) << endl << endl;
    //3029585029808980

    return 0;
}

11
11

262
262

2329
2329

51690500
51690500

5169052
5169052

3029585029808980

just some scratch paper work and you'll realize a pattern here for the strength of numbers... it only returns 2 (odd) , 3 (even, not special) or 4 (even + special)

[helios]

Yes, that's correct. It wasn't at all clear that that's what you meant, in your previous post.