You can do this by regex rewriting the legacy URL as a query. You can do that either on the post_id or the postname, in this case I think the postname is probably safer (avoids false matches on some other path that might start with numbers).
In custom functions, something like this:
add_rewrite_rule( '^[0-9]+/(.*)/?', 'index.php?&name=$matches[1]','top' );
Some similar regex would work in .htaccess or a redirection plugin.
Basically this is rewriting the URL as a query and passing it on to WordPress. WordPress uses this to find the post and then returns the correct permalink as defined in your structure. Essentially it’s two redirects.