Impossible to install with apt-get - python missing

Question

I just updated my Xubuntu to 18.04, and I have no bluetooth anymore. I tried to install blueman and here is the error :

nicolas@nicolas-UX530UX:~$ sudo apt-get install python3
[sudo] password for nicolas: 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
python3 is already the newest version (3.6.5-3ubuntu1).
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.
nicolas@nicolas-UX530UX:~$ sudo apt-get install blueman
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 blueman : Depends: libpython3.6 (>= 3.6.0~b2) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.
nicolas@nicolas-UX530UX:~$ 

As far as I understand it's asking a python > 3.6.0 and as you can see, I have it at 3.6.5.

I tried this also, but no improvement :

sudo apt-get install --reinstall python3

Does anyone have an idea?

UPDATE: I am unable to install anything related to python, so it is not a bluetooth related issue :

nicolas@nicolas-UX530UX:~$ sudo apt-get install krita
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 krita : Depends: libpython3.6 (>= 3.6.4~rc1) but it is not going to be installed
         Recommends: libpython3-dev but it is not going to be installed
         Recommends: python3-pyqt5 but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

UPDATE 2 : I tried to install manually python3.6, and it fails at dependency of libpython3.6-stdlib :

nicolas@nicolas-UX530UX:~$ sudo apt install libpython3.6
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 libpython3.6 : Depends: libpython3.6-stdlib (= 3.6.5-3) but 3.6.6-1+xenial1 is to be installed
E: Unable to correct problems, you have held broken packages.
nicolas@nicolas-UX530UX:~$ sudo apt install libpython3.6-stdlib
Reading package lists... Done
Building dependency tree       
Reading state information... Done
libpython3.6-stdlib is already the newest version (3.6.6-1+xenial1).
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.

UPDATE 3 Here is my list of ppa, but I don't know if I shoudl remove some of them and which one to remove?

nicolas@nicolas-UX530UX:~$ sudo ls /etc/apt/sources.list.d
deadsnakes-ubuntu-ppa-xenial.list            nilarimogard-ubuntu-webupd8-xenial.list.save
deadsnakes-ubuntu-ppa-xenial.list.distUpgrade        ondrej-ubuntu-php-xenial.list
dropbox.list                         ondrej-ubuntu-php-xenial.list.distUpgrade
dropbox.list.distUpgrade                 ondrej-ubuntu-php-xenial.list.save
dropbox.list.save                    skype-stable.list
google-chrome.list                   skype-stable.list.distUpgrade
google-chrome.list.distUpgrade               skype-stable.list.save
google-chrome.list.save                  teamviewer.list
nilarimogard-ubuntu-webupd8-xenial.list          teamviewer.list.distUpgrade
nilarimogard-ubuntu-webupd8-xenial.list.distUpgrade  teamviewer.list.save

Answer 1

Updated
for The following packages have unmet dependencies:

blueman : Depends: libpython3.6 (>= 3.6.0~b2) but it is not going to be installed

you just need installed python3.6 instead python3
try following this commands :

sudo apt-get purge python3.6
sudo apt-get autoremove && sudo apt-get autoclean
sudo apt-get install python3.6*

or you have other version with 3.5 / 3.7, you can run sudo apt-get install libpython3.6=3.6.0~b2

and then reinstall your blueman, with sudo apt-get install --reinstall blueman

Answer 2

For those who are still stuck on reinstalling Python3 after doing some unholy (to Debian) removal of Python3 (and not using the apt-get remove python3 correctly, I offer this 100% recovery step.

https://stackoverflow.com/a/58980420/4379130

Answer 3

It is best if you can avoid purging python3.6 (as per other answer)! This will also remove gnome and other essentials.

Check what Python stuff you have:

apt list --installed | grep python

More specifically, this may help:

apt list --installed | grep python | grep xenial

For example, i had to remove these which were from xenial:

sudo apt remove libpython3.6-minimal libpython3.6-stdlib python3.6-minimal