Prime Construction: Brick Wall

Computer Science Level 5

Imagine that you are an employee of Prime Construction, a company that specializes in building structures based on prime numbers and other mathematical peculiarities. Today, you are tasked with building a brick wall. Each brick has the dimensions $1\times1\times p$ where $p$ is a prime number. You have plenty of each size of brick, but building a wall with just one size of brick would be boring. In fact, building a wall with any two rows the same would be boring, and Prime Construction won't stand for that! If your brick wall must be 100 units tall, and each brick is laid with its longest side parallel to the ground, what is the minimum length the wall can have?

Details and Assumptions

No two rows can have the same exact combination of bricks. For example, if you were building a wall of length $5$ , if you laid down a brick of length $2$ and then one of length $3$ , you couldn't make another row by laying down a $3$ then a $2$ .
The wall must be a perfect rectangular prism with the dimensions $1\times100\times N$ where $N$ is your answer, AKA the minimum length of the wall.
You can't cut the bricks

Image Credit: Prime Construction Corp .

The answer is 31.

1 solution

Garrett Clarke
Jul 15, 2015

This question is equivalent to finding the smallest number that can be written as the sum of prime numbers in at least $100$ distinct ways. According to A000607 , the first number that works is $31$ , as it can be partitioned by prime numbers in $111$ ways.

I was near the solution, I've taken '100 units tall' for the width of the wall.

Here is my solution in python 3.4:

from pyprimes import isprime_naive

primes = []

def nbprimepartitionhelper(m, k):
    global primes
    if m < 0:
        return 0
    elif m == 0:
        return 1
    else:
        return sum(nbprimepartitionhelper(m - primes[j], j)  for j in range(k, len(primes)))

def nbprimepartition(n):
    global primes
    primes = [p for p in range(2, n + 1) if isprime_naive(p)]
    return nbprimepartitionhelper(n,0)

def solve():
    "Prime Construction: Brick Wall"
    n = 2
    while nbprimepartition(n) < 100:
        n += 1
    print(n)

solve()

Abdelhamid Saadi - 5 years, 9 months ago

I don't see why this question is worth 290 points. It was simply a Google search question. Realising the fact at least $100$ distinct ways was trivial.

Kunal Verma - 5 years, 11 months ago

It's worth that much because while the problem may have been a quick google search to you, others may be trying to solve it by hand. So far, less than half of the people who have attempted it have succeeded.

Garrett Clarke - 5 years, 11 months ago

How did you solve it by hand.

Kunal Verma - 5 years, 11 months ago

@Kunal Verma – Oh I used Java! Sorry, my last comment might have been a little misleading. Sure google search is the easy way out, but these problems aren't meant to be solved by scouring the internet for information. Solving a problem like this by hand would be very difficult, but I'm sure there's a way out there! If you can solve a problem by writing a computer program that will do the work for you then I think that's a great solution on it's own. If you can find an answer by hand, that's even better and takes precedence over a computer-driven solution, but if you're the one making the program and it's your brain that does the labor then I think that's just as good of a solution as any!

Garrett Clarke - 5 years, 11 months ago

@Garrett Clarke – I definitely think programming solution might be a possibility. I went on to search for a general solution to prime partitions of n and I found this really good Riemann Zeta approximation but sadly, I'm too dumb to understand. Anyways https://primes.utm.edu/howmany.html.

Kunal Verma - 5 years, 11 months ago

@Kunal Verma – Yeah my Java solution involved making a list of all the prime numbers less than or equal to $N$ , then realizing that a solution for N can only have a make of $N/2$ terms, I started out with the sum of $N/2$ 2s and worked my way down to fewer terms by replacing 2s with 3s, 5s and so on, counting the number of solutions as I went along.

I also saw something really intriguing when searching for the OEIS solution, there's a relationship between the prime partitions and what is known as the Euler Transform, a function that relates two generating functions to one another, you can check that out here (it's the 3rd one).

Garrett Clarke - 5 years, 11 months ago

@Garrett Clarke – Yep I saw that too but I am dumb and I have no wind what happened in that. This problem should definitely be 400 points. Sorry I called it overrated. I feel stupid.

Kunal Verma - 5 years, 11 months ago

@Kunal Verma – Haha no worries! Just next time don't make google your solution hotline lol

Garrett Clarke - 5 years, 11 months ago

I am bad at English. It would have been better if you would have provided this question in the actual question.

Aryan Gaikwad - 5 years, 9 months ago

I'm sorry, I don't understand what you are trying to tell me, could you try to rewrite your comment?

Garrett Clarke - 5 years, 9 months ago

Prime Construction: Brick Wall

Image Credit: Prime Construction Corp .

The answer is 31.

1 solution

0 pending reports