#Mathematica, 140 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter

Mathematica, 140 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter

#Mathematica, 136 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^3];First@SortBy[t,Total])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter

#Mathematica, 140 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter

#Mathematica, 136 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^3];First@SortBy[t,Total])&

.

produces a different shortest addition chain everytime you run it

#Mathematica, 136 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^3];First@SortBy[t,Total])&

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e [71] at the end of the code and press shift+enter