Is there a degree-5 polynomial with integer coefficients and with newly reducible second iterate?

I also did a brute-force search with $|a_i| \leq 6$ for all $i$ and found $$ p(t) = -3t^5 - 3t^4 + 4t^3 + t^2 - 3t + 1, $$ where $p(p(t))$ has the factor $$ 3t^5 - 3t^4 - t^3 + 4t^2 - 3t + 1. $$

The only other example I found in this range was $$ p(t) = -3t^5 + 3t^4 + 4t^3 - t^2 - 3t - 1. $$

Anyways, this either means that I misunderstood the question, or there is an error in your script ;).

I will do a slightly bigger search today to maybe find a monic example.

Added by Peter Mueller (see comments below): Here is the code which does the parallelized search. Save it to a file like par.sage with filename ending in .sage and call sage par.sage. The program will ask for the number of cores to be used, and then starts that many SageMath processes in parallel, logging the progress and the findings to the single file par.log:

import os
from itertools import product
import fcntl

name = sys.argv[0]

def write(text):
    with open(name[:-4] + 'log', 'a') as f:
        fcntl.flock(f, fcntl.LOCK_EX)
        f.write(text + '\n')
        f.flush()
        os.fsync(f.fileno())
        fcntl.flock(f, fcntl.LOCK_UN)
        
if len(sys.argv) == 3:
    N = int(sys.argv[1])
    r = int(sys.argv[2])
    R.<t> = QQ[]
    m = 0
    while True:
        m += 1
        write(f'core = {r}, coefficient bound = {m}')
        l = (range(1, m+1),) + (range(-m, m+1),)*5
        for tup in product(*l):
            if sum(tup) == 0 or sum(tup) % N != r:
                continue
            if tup[-1] == 0 or (min(tup) > -m and max(tup) < m):
                continue
            P = R(tup)
            if not P(t=P).is_irreducible():
                if P.is_irreducible():
                    write(str(P))
else:
    N = int(input('Enter the number of cores to use for the search: '))
    for r in range(N):
        os.system(f'nohup sage {name} {N} {r} &')