Growing Bacteria

[wischi]

Code: Select all

ulong[] Status = new ulong[4];int day = 1;Status[0] = 1;
do{
    for (int i = 3; i > 0; i--)Status[i] = Status[i - 1];
    Status[0] = Status[1]+Status[2];day++;
} while ((Status[0] + Status[1] + Status[2] + Status[3]) <= 1000000000000);
Debug.Write(day);

success

[speedfire]

Thank you Wikipedia !

((1÷√5)(((1+√5)÷2)⁵⁸−((1−√5)÷2)⁵⁸)×2)+(1÷√5)(((1+√5)÷2)⁵⁵−((1−√5)÷2)⁵⁵) = 1,322157322 x10¹²

((1÷√5)(((1+√5)÷2)⁸−((1−√5)÷2)⁸)×2)+(1÷√5)(((1+√5)÷2)⁵−((1−√5)÷2)⁵) = 47

BE CAREFUL : That's doesn't work for the day 1, 2 and 3.

Go to wikipedia to understand more. Sorry but my link would be in French so....

It's 7 a.m so I have to sleep I don't have time to give more informations. But I think it's not so dificult to understand.

[Grusewolf]

I startet with a big solution containing a Bacteria class with age and 'liveOneDay' method, which seem to calculate correct numbers. But it also seemed to be running forever.
So I startet again with this little groovy script. The generations list contains the bacteria generations with 1,2,3 and 4 days old bacterias.

Code: Select all

BigInteger[] generations = [1,0,0,0]
def days = 1
while(generations.sum() < 1000000000000) {
    generations[3] = generations[2]
    generations[2] = generations[1]
    generations[1] = generations[0]
    generations[0] = generations[1..2].sum()
    days++
    println "day $days: population ${generations.sum()}"
}

[Hippo]

Hmmm, excell is good enough for evaluating small Fibbonachi numbers and suming 3 of them as well ...

[elimirks]

There haven't been any recursive solutions posted yet, so here's mine.

By plugging in the numbers, you find a recursive formula: 2T(n-1)-T(n-3), with base cases of T(0)=1, T(1)=2, T(2)=4, T(3)=7, T(4)=11.

I used dynamic programming to speed it up.

Code: Select all

cache = dict()
# n is the number of days
def T(n):
    if n <= 4:
        return [1, 2, 4, 7, 11][n] # Base cases
    elif n in cache:
        return cache[n] # Speed things up with dynamic programming
    return 2*T(n-1) - T(n-3)

amount = 0
day = 0
while amount < 1000000000000:
    amount = T(day)
    cache[day] = amount
    day += 1

print(amount)
print(day)

[NickyKatze]

Oh, that was so so fun to code!

At first I thought what can go wrong with objects. (Insert a warning BUZZ here)! Oh how wrong could have I been. While the object colony was striving and computing I was calculating the memory I needed... well, 1 TB would certanly be enough.

Then I had to use a similar approach that was already posted earlier :3

[adark]

I gotta admit, this puzzle is actually a lot easier to do than anticipated. xD

Here's my Lua:

Code: Select all

local current = {0, 1, 0, 0}

local i = 0
while true do
	i = i + 1
	current = {current[1] + current[2], current[1], current[2], current[3]}
--[[if i == 8 then
		print(current[1] + current[2] + current[3] + current[4])
		break
	end
--]]
	if current[1] + current[2] + current[3] + current[4] >= 1000000000000 then
		print(i)
		break
	end
end

I guessed that the 'unique' bacterium wasn't going to be in the first 'day' of its cycle, and it turns out I was right on the first try, lol.

[a.goth]

The problem can even be solved in terms of a closed-form expression:

The population size N ≥ 4 is reached after

    ⌈log(N - ½) / log(φ)⌉

days, where φ is the golden ratio and ⌈x⌉ denotes the ceiling function.

Math is your friend!

[0x1d1aN]

I used two Fibonacci sequences {1,2,3,5,8,13..}
First sequence is representing number of daily born (add to total living), and second sequence starts at the 5th day, and representing count of dead (subtract from total living).

Code: Select all

fib_born = [0, 1]
fib_dead = [0, 1]

day = 1
living_count = 0

while living_count < 1000000000000:
  fib_born = [fib_born[1], fib_born[0] + fib_born[1]]
  living_count += fib_born[0]

  if day > 4:
    fib_dead = [fib_dead[1], fib_dead[0] + fib_dead[1]]
    living_count -= fib_dead[0]

  print day, living_count
  day += 1

print "END"

[konkor]

The first post so far, hope it would be in a good place here! Thanks!
Feel free to comment on my solution, I am just a student yet. )

Code: Select all

import java.math.BigInteger;

public class Bacteria {
	
	// Returns n-th Fibonacci number
    static BigInteger fib( int n )
    {
        BigInteger a = BigInteger.valueOf( 0 );
        BigInteger b = BigInteger.valueOf( 1 );
        BigInteger c = BigInteger.valueOf( 1 );
        for ( int j = 2; j <= n; j++ )
        {
            c =  a.add( b );
            a = b;
            b = c;
        }
 
        return ( a );
    }
	
	
	public static void main(String[] args) {
		
		BigInteger population = new BigInteger("0");
		int day = 0;
		BigInteger die = new BigInteger("0");
		int count = 0;
		
		do {
			day ++;
			population = population.add( fib(day) ).subtract(die);
			if( day >= 5 ) {
				count++;
				die = die.add( fib(count) );
			}
			//System.out.println(population + " Day: " + day);
		}while(population.compareTo( new BigInteger("1000000000000") ) < 0);
		
		if(population.compareTo( new BigInteger("1000000000000") ) > 0){
		    day--;
		}
		System.out.println("Day: " + day);
	}

}