Project Euler P76: Counting Arrangements of Consecutive Numbers

In summary, the purpose of Project Euler P76 is to solve the problem of counting the number of ways to express a given integer as a sum of consecutive integers. This can be achieved by using a dynamic programming approach with a time complexity of O(n^2). The solution can also be optimized further using a sliding window technique. Additionally, there are real-world applications for this solution, such as scheduling tasks, allocating resources, and arranging objects in a given space.
  • #1
Arman777
Insights Author
Gold Member
2,168
193
TL;DR Summary
How many different ways to write the 100.
Python:
import time
start = time.perf_counter()

def con(H):
    J = []
    Q = []
    W = []
    for i in H:
        for j in range(len(i)-1):
            Cop = i[::]
            y = i[j]+i[j+1]
            del Cop[j:j+2]
            Cop.insert(j,y)
            J.append(Cop)
    for i in J:
        y =(sorted("".join(str(j) for j in i)))
        Q.append("".join(y))
    T = list(set(Q))
    for i in T:
        y = [int(j) for j in i]
        W.append(y)
    return W

for num in range(1,100):
    K = [[1 for i in range(num)]]
    count = 0
    for i in range(len(K[0])-2):
        K = con(K)
        count = count + len(K)
    print(num,count+1)
    end = time.perf_counter()
    print(end-start,"second")

Here what this code does, For example, let us say num = 4. Then it creates an array of

[[1,1,1,1]]. Then it sums the consecutive numbers so our result becomes (from line 9-14)

[[2,1,1],[1,2,1],[1,1,2]] Since they are all same my code (from line 15-18) makes them just one function and returns ["112"] and then from 18-21 turns ["112"] to [[1,1,2]] and then I do this whole process again for the [[1,1,2]] and then I count the number of these arrays (from 25-29). The problem is its fast up to num = 20-30 but then it really slows down. Is there a way to increase the speed of my code or should I try a different algorithm?

Thanks.

For num = 5 the number should be 6
(1,1,1,1,1)
(2,1,1,1)
(2,2,1)
(3,2)
(3,1,1)
(4,1)

My code is correct bu just works slow.
 
Last edited:
Technology news on Phys.org
  • #2
First, at no time do you mention the words "sum of integers". You are making us figure out what the problem is instead of writing it clearly. Please have more respect for our time.

Second, what algorithm? I see a mess of uncommented code, bit no description of what you are thinking about. I suppose we could eventually figure it out, but please have more respect for our time.

Third, yes, there is a better algorithm. My code (14 lines of C++) gets the answer in 2 milliseconds.
 
  • #3
I have already explained my code. I gave an example for 5. I think I was pretty clear.
Vanadium 50 said:
My code (14 lines of C++) gets the answer in 2 milliseconds
Indeed there's an better algorithm but I am asking about my code and how can I improve it. Not some other solutions line number or time.
 
  • #4
I must agree with @Vanadium 50 , the goal could be defined in a more clear way. However with some little of guessing I think I understand what result you expect (actually deducing from your example num=5).
If you don't need to list all the possible combinations of the relative integers, you can solve the problem by using combinatorics, and using numpy arrays in order to avoid slow python loops.

Try this code:
Python:
import numpy as np
from scipy.special import binom

# input
num = 5
n = np.arange(2, num+1)
x = binom(num-1, num-n) / binom(n,1)
# output
print(np.sum(np.ceil(x)))
 
  • #5
lomidrevo said:
I must agree with @Vanadium 50 , the goal could be defined in a more clear way. However with some little of guessing I think I understand what result you expect (actually deducing from your example num=5).
If you don't need to list all the possible combinations of the relative integers, you can solve the problem by using combinatorics, and using numpy arrays in order to avoid slow python loops.

Try this code:
Python:
import numpy as np
from scipy.special import binom

# input
num = 5
n = np.arange(2, num+1)
x = binom(num-1, num-n) / binom(n,1)
# output
print(np.sum(np.ceil(x)))
This is calculating wrong. For 6 there are 10 different ways. Your code gives 12
 
  • #6
Arman777 said:
I think I was pretty clear.

You weren't. The problem is to figure out how many different ways there are of writing the number 100 as a sum of two or more positive integers. "How many different ways to write 100" does not clearly communicate that.

Also, this is an Euler problem, and solutions aren't supposed to be publicly visible. So I am closing this thread.
 

Related to Project Euler P76: Counting Arrangements of Consecutive Numbers

1. What is Project Euler P76?

Project Euler P76 is a mathematical programming challenge that involves finding the number of ways in which a given integer can be expressed as a sum of consecutive positive integers.

2. How does Project Euler P76 work?

Project Euler P76 requires the use of mathematical concepts such as partitioning and generating functions to find the number of arrangements of consecutive numbers. It is solved by writing a computer program that can efficiently calculate the solutions for large numbers.

3. What are the main challenges of solving Project Euler P76?

Some of the main challenges of solving Project Euler P76 include finding an efficient algorithm to calculate the solutions, handling large numbers, and optimizing the code for speed and memory usage.

4. What are the benefits of solving Project Euler P76?

Solving Project Euler P76 can improve problem-solving skills, increase familiarity with mathematical concepts, and improve programming skills. It can also provide a sense of accomplishment and satisfaction.

5. Are there any resources available for solving Project Euler P76?

Yes, there are various resources available such as online forums, blogs, and websites that provide hints, tips, and solutions for Project Euler problems. However, it is recommended to try solving the problem independently before seeking help from these resources.

Similar threads

  • Programming and Computer Science
Replies
34
Views
3K
  • Programming and Computer Science
3
Replies
97
Views
7K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
10
Views
1K
Replies
1
Views
2K
  • Programming and Computer Science
Replies
10
Views
790
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
14
Views
2K
  • Engineering and Comp Sci Homework Help
3
Replies
80
Views
8K
  • Programming and Computer Science
Replies
1
Views
1K
Back
Top