Entries tagged with algorithm - Channel 8

Puzzle series: Addition of Four Primes

Miguel — Sat, 05 Jan 2008 15:28:00 GMT

Ok, after a vacation week I am back, this is my first post of 2008 and also my first post with the new look&feel of the website. I wish all of you a Happy New Year and also hope you like the new website design...

Let's continue on our series about Algorithms and Math puzzles. I want to propose you to take a look at prime numbers.

There are some conjectures that state properties of these numbers. One of those conjectures is the Waring's prime number conjecture, it states that every odd integer is either prime or the sum of three primes.

Probably, the most famous conjecture about prime numbers is the Goldbach's Conjecture, and claims that every even integer is the sum of two primes.

Both problems have been studied for over 200 years...

In this problem, you have a little different task: You have to find a way to express a given integer as the sum of four primes (exactly four).

Consider an input of an integer (n<10000000), you should return a list with the four prime numbers. If it is impossible to represent that, you can give as output any illogical result (i.e: -1 -1 -1 -1)

Example:

Input: 24
Output: 3 11 3 7

As you can see, you can repeat prime numbers as factors for a given input, and it does not matter if the list of factors is ordered or not.

What kind of algorithm would you implement? Is it efficient? Remember: Most powerful weapons of human's mind are Mathematics and Logic ;-)

Enjoy and comment, good luck folks! :-)

Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 00:55:00 GMT

Hi there,

I want to propose you a kind of algorithm/mathematics problem, mixed with some fun related with this Christmas period... :-)

Imagine that you have a big Christmas tree with 365 light bulbs, each one with a switch, tagged with correlative numbers from 1 to 365. During December 25th on 2006, you looked at the tree and saw all lights OFF, so you decided to switch them but in a particular way.

Each day of the year (assuming 365 days) you would change the state of each switch just one time, according to a certain rule. The rule is that during the day “n” I will only switch those bulbs tagged with a number multiple of this “n” value.

Giving you an example to clarify this criteria:

1^st day: All bulbs multiple of 1. So, all bulbs. (the tree was beautiful that night, completely lightened)

2^nd day: All bulbs multiple of 2. So… #2, #4, #6, #8… (notice that this day all bulbs multiple of 2 were switched off)

3^rd day: All bulbs multiple of 3. So… #3, #6, #9…

Last day: All bulbs multiple of 365. So… only the #365.

Assuming that anything strange happens and nobody except you touches the switchs, which bulbs will be ON today? How would you determine it?

Merry Christmas from the whole Channel 8 Team :-)

Fascinating algorithm to resize pictures

littleguru — Wed, 29 Aug 2007 15:37:00 GMT

Dr. Ariel Shamir from Efi Arazi School of Computer Science is one of the co-inventors of a clever algorithm to resize images. Usually if you have an image that is to big in size you crop or resize it. Now if you resize it, important information might get lost because some pieces in the picture are getting to tiny that you can't see them anymore (they might even get at a sub pixel level where they are merged with other pixels). On the other hand if you crop the image, parts are missing completely. That could also include important information! Another problem would be two hot spots in an image: you would need to crop and merge the two pieces somehow, which isn't always an easy task.

Now the people around Dr. Shamir invented a way to resize pictures without losing important details. They have published a video on how their algorithm works. The paper describing the whole algorithm and ideas is found here.

A few days ago Dr. Shamir has been hired by Adobe. Wouldn't it be very cool if we would get the algorithm as a feature in one of the next Photoshop versions?