Problem 214

[Bhilal]

excuse me but I must write the answers which i found in order to show my mistake

13238273
13631489
16121857
16384001
18841601
19824641
20054017
21626881
22806529
23789569
24576001
27688961
28311553
29884417
35200001
35389441
35684353
38535169

sum of them are 441588754. But it seems incorrect. here is my Eulerfi function. where is my mistake?

Code: Select all

 public static int Eulerfi(int n)
    {
        if(isprime(n))
            return n-1;
        
        Set set = new HashSet();
        int hasil = 1;
        int cem = 1;
        int a = n;
        
        for(int i=2; i<=n; i++)
        {
            if(n%i==0 && isprime(i))
            {
                n /= i;
                set.add(i);
                hasil *= (i - 1);
                cem *= i;
            }
           
        }
        
        return a*hasil/cem;
    }

[Eigenray]

The values you found are correct but there are thousands more that you're missing, for example 9548417.

return a*hasil/cem;

It looks like you have an overflow here.

[Bhilal]

Thanks I found my mistake just overflow

[xe3tec]

Need a little help here too.

As far as I can see my algo is correct and the numbers are correct and it also checks for the correct length of the chain.
But I got like a million numbers, and the sum would be a 13-digit number...

e.g.

[38535169, 38535168, 11010048, 3145728, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096,
2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

first number is prime, and the len of the chain ist 25

is that correct?

[jaap]

But I got like a million numbers, and the sum would be a 13-digit number...

There are very many length 25 chains, and the correct answer does have 13 digits.
There are for example 7 chains with a starting number 38535xxx:
38535169, 38535197, 38535221, 38535473, 38535521, 38535703, 38535947

[xe3tec]

Thx, I got it...

I forgot 1 Number *faceplam* because of this it was incorrect the first time

that wasent such a difficult problem

not solved under a minute though :/ took me 6mins