Thread: Algo to check for recurring cycles in an array

Hi guys,

I`m trying to solve euler`s 26th problem but I`m stuck... The thing is I`ll have an array filled with integers and I want to see if there is a recurring cycle in it.

1/7 = 0.142857142857142857(..) (142857 is the recurring cycle)

So my array will be 142857142857142857(...) (to infinity since I don`t know when to stop calculating)

If only I knew how long the cycle is I would be able to solve the problem... But I can`t really tell when the cycle is over because it could be like 0.1412345 or something like that where there are repeating digits

I`m sorry if this post is too confusing but it`s hard for me to describe the problem...

Any help will be apreciated!

Code:

#include <stdio.h>

int main(int argc, char *argv[])
{
    div(1,8);
    getch();
    return 0;
}

int div (int a, int b)
{
    int i, lastI, chain[1000], index = 0;
    while (a > 0)
    {
        if (a < b)
           a *= 10;
        else
        {
            for (i = 1; b*(i+1) <= a; i++){}
            a -= b*i;
            
            chain[index++] = i;
        
           printf("%d", i);
        }
    }
    return 0;
}

This is what I have so far... Just a division function

I hope you will notice that Project Euler is often not really meant to test your programming skills, but really your problem solving skills. As such, many of the problems can be solved easily using a pencil and paper.

Problem 26 is a great example of one that really doesn't require you to write a program. In fact, a couple keen observations and some lucky guesses could have had the problem solved in a couple minutes, maybe even less.

I'm sorry if this doesn't seem helpful, but Project Euler is really all about helping you develop your problem solving skills. If you jump into every problem trying the bruteforce method immediately, you're going to miss out on a lot of elegant math, and you probably won't learn much (which might hurt you as you reach the later problems).

I'm sorry guys but I couldn't solve it. Is there an article or something like that I could read?
I have no deep math knowledge (just started studying engineering tough) and I find most of the "complex" problems pretty much impossible to do. I'm also trying to do problem 31 and found that I need to implement some sort of greedy algorithm. I even read about it, but I'm still clueless heh

I really want to learn as I find these problems quite interesting, but right I'm getting more frustrated. Just for you to see that I'm not slacking here's my profile: http://projecteuler.net/index.php?se...&profile=Bruno

There's not much help in euler's forums and that really sucks. I think they're more concerned in testing you than in educating you.

iMalc

I tried doing like 1/7*7*7 and 1/7*7*7*2 (none worked) but how can I know if increasing the divisor will also increase the size of the cycle?

Trust me, I totally understand your frustration. I've completed about ~180 of the problems on that site (which at one point was almost 100%), but I find that now most of the problems are out of my league. At best, I think I can solve about 4 more.

And I believe the most frustrating part is that the site is intended to help you learn, and yet makes no effort to help you at all. They just propose a problem, and if you can't solve it... tough. There is a great deal of satisfaction though when you encounter a tough problem, struggle with it for hours, and then solve it entirely on your own.

So here is my effort to help you without completely giving away the answer:

First, I'll look at the examples they gave you that result in a repeating decimal and divide them into two groups.

Group 1) 1/3, 1/6, 1/9
Group 2) 1/3, 1/7

Observations:

All the fractions in group one result in repeating decimals with a cycle length of one. Why do you suppose that is? Is there something all those numbers have in common?

The fractions in group two also result in repeating decimals, with 1/7 having considerably more than 1/3. What special property do these fractions have in common?

And a question: do you think the answer (1/p) is going to have a large p or a small p, based on these observations?

Finally, I'm sure in grade school you were taught an easy way to create a repeating decimal. For example, if you want repeating 1's, divide 1/9. If you want repeating 7's, divide 7/9. If you want repeating 142857, divide 142857/999999.

But wait... 142857 was the repeating cycle in 1/7... so that means:

Code:

1   142857
- = ------
7   999999

And you might be able to derive a useful conclusion from that as well.

Based on everything I showed you, I was able to come up with a guess and check strategy that led me to the answer in less than 2 minutes.

If you still can't get anywhere, try doing some online research into "repeating decimals".

The observation about group 1 that I wanted you to notice is that they are all multiples of three. The only thing this pointed out to me was that simply picking a large multiple of a number that gives a repeating decimal is not a good strategy. In other words, 1/3 gives a repeating decimal, but don't think that 1/(3 * N) for some large N is necessarily going to be better.

The only observation about group 2 that you should notice is they are prime. Prime numbers have a tendency to appear in these problems. Considering they have no factors at all, its easy to see how they would tend to create long cycles when repeated divisions are performed.

Regarding the equation I showed you, if a fraction is going to produce a repeating decimal, than it can be written as some integer N over a series of 9's. Write 1/p this way.

Code:

1    N
- = ---
p   9's

Cross multiply:

9's = p * N

The number of 9's has to be equal to the number of digits in N. If you looked at the Wikipedia page for repeating decimals, or just checked a bunch of example primes, you'll notice a pattern. Some of them produce cycles of length (p-1) while others produce smaller cycles. Obviously we don't care about the smaller ones. If (p-1) is the max length they can produce, that's what we care about.

Popping that into the cross multiplied equation we derived above we can see that for any p we select, the largest cycle possible will be of length (p-1):

Code:

10^p - 1 = p * N

10^p - 1 is the same as (p-1) 9's

What does that equation tell us? Well, if we pick some prime number p, and (1/p) produces a repeating cycle of length (p-1), then p must divide evenly into (10^p - 1). Furthermore, (10^p - 1) / p will give you the digits in the cycle.

At this point, I don't really think I can tell you any more without completely giving away the answer.