programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Jeanne Boyarsky
• Liutauras Vilda
Sheriffs:
• Rob Spoor
• Bear Bibeault
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Piet Souris
Bartenders:
• Frits Walraven
• Himai Minh

# Problem 382 of Euler project

Ranch Hand
Posts: 3851
• Number of slices to send:
Optional 'thank-you' note:
Hi,

I am trying to solve Problem 382 of Euler project - http://projecteuler.net/problem=382
One of the steps to solve this problem (with my logic) is, if you get an array of some numbers, you've to generate unique combinations from those numbers, minimum 3 numbers in a set. For example, if an array given is: 1 2 3 4 6.

The combinations will be:

1 2 3 4 6
2 3 4 6
3 4 6
2 4 6
2 3 6
2 3 4
1 3 4 6
1 4 6
1 3 6
1 3 4
1 2 4 6
1 2 6
1 2 4
1 2 3 6
1 2 3
1 2 3 4

I could write algorithm for it but it's not efficient. It takes hours to generate combinations from an array of 25 numbers. Here is my code:

I am sure there could be many improvements in it or this algorithm whole could be discarded...

Thanks.

ankur rathi
Ranch Hand
Posts: 3851
• Number of slices to send:
Optional 'thank-you' note:
Also placing problem here for those who don't want to register...

A polygon is a flat shape consisting of straight line segments that are joined to form a closed chain or circuit. A polygon consists of at least three sides and does not self-intersect.

A set S of positive numbers is said to generate a polygon P if:

no two sides of P are the same length,
the length of every side of P is in S, and
S contains no other value.

For example:
The set {3, 4, 5} generates a polygon with sides 3, 4, and 5 (a triangle).
The set {6, 9, 11, 24} generates a polygon with sides 6, 9, 11, and 24 (a quadrilateral).
The sets {1, 2, 3} and {2, 3, 4, 9} do not generate any polygon at all.

Consider the sequence s, defined as follows:

s1 = 1, s2 = 2, s3 = 3
sn = sn-1 + sn-3 for n > 3.

Let Un be the set {s1, s2, ..., sn}. For example, U10 = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.
Let f(n) be the number of subsets of Un which generate at least one polygon.
For example, f(5) = 7, f(10) = 501 and f(25) = 18635853.

Find the last 9 digits of f(1018).