TL;DR
dpkg -r PACKAGE1 PACKAGE2 PACKAGE3 ...
Short explaination:
dpkg -r
removes an installed package without removing the config files.
In this case, dpkg -r did not perform a real "uninstall", since the packages were not installed through dpkg or apt.
It simply removed some leftover files or entries on Marco's PC - I wasn't able to find the information on where these entries could be stored other than under "/var/lib/dpkg/info".
There may be other explainations possible, and I don't know how exactly this situation would happen in the first place.
Not sure if any of these will help you, but it's worth a try.
Check if dpkg sees the packages:
dpkg -l '*python3.5*'
mark to remove:
dpkg-remove PACKAGE_NAME
apt-update
remove or purge through dpkg:
dpkg -r python3.5
dpkg -P python3.5
Double check if there are any files in /var/lib/dpkg/info
ls -al /var/lib/dpkg/info/ | grep python3
Clean packages thorugh apt-get:
sudo apt-get autoclean
sudo apt-get autoremove
sudo apt-get clean
I've also come across this bash script:
https://github.com/epinna/Unusedpkg
If anything happened, reboot the PC afterwards.
EDIT
I can find all of these 4 packages through apt
on ubuntu 20:
libarchive13:amd64
libnm0:amd64
python3-zope.interface
network-manager
I suggest you simply try to reinstall these 4.