Esta pergunta foi respondida por @edwinksl aqui: link
A versão 3.6 do Python parece não ter sido adicionada aos repositórios oficiais do Ubuntu 16.04 LTS. No entanto, existem outros que criaram repositórios para ele, entre eles J Fernyhough. Você pode adicionar e instalar o Python 3.6 através de seu repositório:
sudo add-apt-repository ppa:jonathonf/python-3.6
sudo apt-get update
sudo apt-get install python3.6