Perhaps the simplest thing of all is to use a “parallel” \mark system; we have learnt to be well-behaved, so we now allocate the \marks number with \newmarks.
\documentclass[a4paper,twoside]{article}
\usepackage[T1]{fontenc} % Not necessary, but recommended.
\usepackage{etoolbox}
% \usepackage{amsthm} % doesn't call "\@opargbegintheorem", though
\usepackage{fancyhdr}
\usepackage{lipsum}
\fancyhf{}
\fancyhead[LE,RO]{\thepage}
\fancyhead[RE,LO]{\myBotmark} % "RE" just for testing purposes
\pagestyle{fancy}
\newtheorem{theorem}{Theorem}[section] % or "[chapter]", or whatever
\newtheorem{lemma} {Lemma} [section]
\makeatletter
\@ifdefinable\@my@claim@mark{\newmarks\@my@claim@mark}
\newcommand*\myMark[1]{\marks\@my@claim@mark{#1}}
\newcommand*\myBotmark{\botmarks\@my@claim@mark}
\apptocmd{\@begintheorem} {\myMark{#1\ #2}\ignorespaces}{}{}
\apptocmd{\@opargbegintheorem}{\myMark{%
#1\ #2%
\ (#3)% comment this line to leave "Mickey Mouse" out
\ignorespaces
}}{}{}
\makeatother
\begin{document}
\section{First section}
\lipsum[1]
\begin{theorem}
This is the first theorem of the first section.
\end{theorem}
\lipsum[2]
\begin{theorem}
This is the second theorem of the first section.
\end{theorem}
\begin{theorem}[Donald Duck]
This is the third theorem of the first section.
\end{theorem}
\lipsum[3-16]
\begin{theorem}
This is the fourth theorem of the first section.
\end{theorem}
\lipsum[17]
\begin{lemma}
This is the first lemma of the first section.
\end{lemma}
\lipsum[18]
\begin{theorem}
This is the fifth theorem of the first section.
\end{theorem}
\lipsum[19-20]
\begin{lemma}[Uncle Scrooge]
This is the second lemma of the first section.
\end{lemma}
\lipsum[21-32]
\begin{theorem}
This is the sixth theorem of the first section.
\end{theorem}
\lipsum[33-36]
\begin{theorem}
This is the seventh theorem of the first section.
\end{theorem}
\begin{lemma}
This is the third lemma of the first section.
\end{lemma}
\begin{theorem}[Mickey Mouse]
This is the eighth theorem of the first section.
\end{theorem}
\lipsum[37-40]
\begin{theorem}
This is the ninth theorem of the first section.
\end{theorem}
\lipsum[41-64]
\begin{theorem}[The last one]
This is the tenth theorem of the first section.
\end{theorem}
\lipsum[65-80]
\begin{lemma}
This is the fourth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fifth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the sixth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the seventh lemma of the first section.
\end{lemma}
\begin{lemma}
This is the eighth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the ninth lemma of the first section.
\end{lemma}
\begin{lemma}[Deep breath]
This is the tenth lemma of the first section.
\end{lemma}
\lipsum[81-84]
\begin{lemma}
This is the eleventh lemma of the first section.
\end{lemma}
\begin{lemma}
This is the twelfth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the thirteenth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fourteenth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fifteenth lemma of the first section.
\end{lemma}
\begin{lemma}[Hexadecimal deep breath]
This is the sixteenth lemma of the first section.
\end{lemma}
% \lipsum[85-96]
\end{document}
Cannot post an image: compile and look at the output.
Addition
Actually, the OP had made it very clear, in the question, that (s)he was using the amsthm package, but I overlooked this statement. The code shown above should also work when that package is loaded, but in that case the running heads will omit the “theorem note”, that is, the optional argument given to “theorem-like environments” (e.g., “Donald Duck” in the third theorem of our example) when present. This is because the amsthm package does not use the standard \@opargbegintheorem hook.
For this as well as for other reasons, it is best to devise another patch specifically suited for the amsthm package, that delivers the mark in the argument of the \deferred@thm@head macro, which is typeset inside of \box\@labels; more precisely, it is emitted right before the call to either \swappedhead or \thmhead, at the very beginning of \box\@labels. Note that this box is subsequently \unhboxed, so the mark will wind up at the very beginning of the horizontal list that contains the theorem head, followed by the theorem claim; from there, it will migrate right after the first line of the same paragraph, that is, exactly where it belongs to.
The following code defines a command named \IfAmsThm that takes two arguments, and executes the code in its first argument if the amsthm package is loaded, and the code in its second argument if it is not. Of course, once you have made your decision, you no longer need this device: simply delete this command and either of the two branches that does not apply.
In order to use this code in your documents you need to do only the following three things:
make sure to load the etoolbox package early in your preamble;
copy the code between the two comments BEGIN WIZARDRY and
END WIZARDRY to your preamble, at a point in which both
the etoolbox package and the amsthm package have already
been loaded;
in the definition of your page style, put \myBotmark wherever
you want the theorem reference to appear (similar to putting
\thepage wherever you want the page number to appear).
Here is the amended code:
\documentclass[a4paper,twoside]{article}
\usepackage[T1]{fontenc} % Not necessary, but recommended.
\usepackage{etoolbox}
\usepackage{amsthm} % comment or uncomment as you prefer
\usepackage{fancyhdr}
\usepackage{lipsum}
\fancyhf{}
\fancyhead[LE,RO]{\thepage}
\fancyhead[RE,LO]{\myBotmark} % "RE" just for testing purposes
\pagestyle{fancy}
\newtheorem{theorem}{Theorem}[section] % or "[chapter]", or whatever
\newtheorem{lemma} {Lemma} [section]
% A little trick to make this example work both with amsthm and without it;
% once you've made your choice, you do not need this code.
\makeatletter
\@ifdefinable\IfAmsThm{}
\@ifpackageloaded{amsthm}{
\let \IfAmsThm = \@firstoftwo
}{
\let \IfAmsThm = \@secondoftwo
}
\makeatother
\IfAmsThm{
\newtheorem*{spclaim}{Special Claim}
\theoremstyle{definition}
}{}
\newtheorem{defin}{Definition}[section]
%%%%%%%% BEGIN WIZARDRY %%%%%%%%
\makeatletter
\@ifdefinable\@my@claim@mark{\newmarks\@my@claim@mark}
\newcommand*\myMark[1]{\marks\@my@claim@mark{#1}}
\newcommand*\myBotmark{\botmarks\@my@claim@mark}
\typeout{****************************************}
\@ifpackageloaded{amsthm}{\iftrue}{\iffalse}
\patchcmd{\@begintheorem}{% search for:
\thm@swap\swappedhead\thmhead % more specific than before
}{% replace with:
\myMark{#1\@ifnotempty{#2}{\ #2}\@ifnotempty{#3}{\ (#3)}}%
\thm@swap\swappedhead\thmhead
}{
\typeout{>>> Made patch specific for amsthm.}
}{
\typeout{>>> Patch specific for amsthm FAILED!}
}
\else
\apptocmd{\@begintheorem} {\myMark{#1\ #2}\ignorespaces}{}{}
\apptocmd{\@opargbegintheorem}{\myMark{%
#1\ #2%
\ (#3)% comment this line to leave "Mickey Mouse" out
\ignorespaces
}}{}{}
\typeout{>>> Made generic patch.}
\fi
\typeout{****************************************}
\makeatother
%%%%%%%% END WIZARDRY %%%%%%%%
\begin{document}
\section{First section}
\lipsum[1]
\begin{theorem}
This is the first theorem of the first section.
\end{theorem}
\lipsum[2]
\begin{theorem}
This is the second theorem of the first section.
\end{theorem}
\begin{theorem}[Donald Duck]
This is the third theorem of the first section.
\end{theorem}
\IfAmsThm{
\begin{spclaim}
This is a special claim.
\end{spclaim}
}{}
% \begingroup
% \showboxbreadth = 1000
% \showboxdepth = 10
% \tracingonline = 1
% \showlists
% \endgroup
\lipsum[3-16]
\begin{theorem}
This is the fourth theorem of the first section.
\end{theorem}
\begin{defin}[Something new]
This is the first definition of the first section.
\end{defin}
\begin{defin}
This is the second definition of the first section.
\end{defin}
\lipsum[17]
\begin{lemma}
This is the first lemma of the first section.
\end{lemma}
\lipsum[18]
\begin{theorem}
This is the fifth theorem of the first section.
\end{theorem}
\lipsum[19-20]
\begin{lemma}[Uncle Scrooge]
This is the second lemma of the first section.
\end{lemma}
\lipsum[21-32]
\begin{theorem}
This is the sixth theorem of the first section.
\end{theorem}
\lipsum[33-36]
\begin{theorem}
This is the seventh theorem of the first section.
\end{theorem}
\begin{lemma}
This is the third lemma of the first section.
\end{lemma}
\begin{theorem}[Mickey Mouse]
This is the eighth theorem of the first section.
\end{theorem}
\lipsum[37-40]
\begin{theorem}
This is the ninth theorem of the first section.
\end{theorem}
\lipsum[41-64]
\begin{theorem}[The last one]
This is the tenth theorem of the first section.
\end{theorem}
\lipsum[65-80]
\begin{lemma}
This is the fourth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fifth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the sixth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the seventh lemma of the first section.
\end{lemma}
\begin{lemma}
This is the eighth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the ninth lemma of the first section.
\end{lemma}
\begin{lemma}[Deep breath]
This is the tenth lemma of the first section.
\end{lemma}
\lipsum[81-84]
\begin{lemma}
This is the eleventh lemma of the first section.
\end{lemma}
\begin{lemma}
This is the twelfth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the thirteenth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fourteenth lemma of the first section.
\end{lemma}
\begin{lemma}
This is the fifteenth lemma of the first section.
\end{lemma}
\begin{lemma}[Hexadecimal deep breath]
This is the sixteenth lemma of the first section.
\end{lemma}
% \lipsum[85-96]
\end{document}
As before, there’s little point in posting an image showing the result: you must compile the code yourself and check that it behaves as expected.
Second Addition
See my answer to the question Place theorem number before theorem label in page header for an improved version of the code that provides compatibility with the \swapnumbers feature.
titlepspackage seems to have tools for that. You can take a look at§ 7, Extra marksin the documentation. – Bernard Jul 14 '16 at 23:29