My vim does not support python3, how can I fix this [duplicate]

Question

So I want jedi-vim to autocomplete to python3, I added

autocmd FileType python set omnifunc=python3complete#Complete

To my vimrc. Now if I try and autocomplete something in vim I get

Error: Required vim compiled with +python3
E117: Unknown function: python3complete#Complete

And if I check my vim version I get

vim --version |grep python
+cryptv          +linebreak       +python          +vreplace
+cscope          +lispindent      -python3         +wildignore
Linking: gcc   -L. -Wl,-Bsymbolic-functions -Wl,-z,relro -fstack-protector -rdynamic -Wl,-export-dynamic -Wl,-E  -Wl,-Bsymbolic-functions -fPIE -pie -Wl,-z,relro -Wl,-z,now -Wl,--as-needed -o vim        -lm -ltinfo -lnsl  -lselinux  -lacl -lattr -lgpm -ldl  -L/usr/lib -llua5.2 -Wl,-E  -fstack-protector-strong -L/usr/local/lib  -L/usr/lib/x86_64-linux-gnu/perl/5.22/CORE -lperl -ldl -lm -lpthread -lcrypt -L/usr/lib/python2.7/config-x86_64-linux-gnu -lpython2.7 -lpthread -ldl -lutil -lm -Xlinker -export-dynamic -Wl,-O1 -Wl,-Bsymbolic-functions  -L/usr/lib/x86_64-linux-gnu -ltcl8.6 -ldl -lz -lpthread -lieee -lm -lruby-2.3 -lpthread -lgmp -ldl -lcrypt -lm   

Which I assume means I lack python3 support in vim?

I cannot work out how to fix this, what ought I to do?

I am running (and have always had) ubuntu 16.04. Python3 is managed by pip, I have no other issues with it.