<?php
ini_set('memory_limit', '256M');

function palindrome($half) {
    return $half.strrev($half);
}

function solve($n, $dnaSet) {
    $results = $parents = $childs = [];
    $parentSize = $childSize = $i = $k = $x = 0;
    $d = count($dnaSet);

    while($i < $n) {
        $i++;

        //Rotate DNA
        if ($i>1) {
            $x = ($x+1)%$d;
        }
        $dna = $dnaSet[$x];

        //Adam Eva (First generation)
        if ($i <= 2) {
            $parents[] = $dna;
            $childSize = count($parents) * 2;
            $results[] = palindrome($dna);
            continue;
        }

        //Make baby (Grow)
        $gen = $parents[floor($k/2)] . $dna;
        $childs[] = $gen;
        $k++;
        $results[] = palindrome($gen);
        
        //Recycle (Made children next generation)
        if ($childSize && $k === $childSize) {
            $parents = $childs;
            $childs = [];
            $k = 0;
            $childSize *= 2;
        }
    }
    
    return $results;
}

$n = 1000000;
$dnaSet = ['4', '5'];
$rs = solve($n, $dnaSet);
var_dump(array_pop($rs));
echo PHP_EOL;