\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage{dsfont}
\def\lcm{\operatorname{lcm}}
\def\C{{\mathds{C}}}
\def\N{{\mathds{N}}}
\def\Re{\mathop{\mathrm{Re}}}
\def\Reg{\operatorname{Reg}}

\usepackage{maple2e}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}



\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{rem}[theorem]{Remark}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf A Survey of Gcd-Sum Functions} \vskip 1cm
\large L\'aszl\'o T\'oth \\
Department of Mathematics \\
University of P\'ecs \\
Ifj\'us\'ag u. 6 \\
7624 P\'ecs \\
Hungary \\
\href{mailto:ltoth@gamma.ttk.pte.hu}{\tt ltoth@gamma.ttk.pte.hu}\\
\end{center}

\vskip .2 in

\begin{abstract} 
We survey properties of the gcd-sum function and of its analogs.
As new results, we establish asymptotic formulae with remainder
terms for the quadratic moment and the reciprocal of the gcd-sum
function and for the function defined by the harmonic mean of the
gcd's.
\end{abstract}

%************************* section 1 *******************************************

\section{Introduction}

The gcd-sum function, called also Pillai's arithmetical function, is
defined by
\begin{equation} \label{P_def}
P(n)=\sum_{k=1}^n \gcd (k,n).
\end{equation}

By grouping the terms according to the values of $\gcd (k,n)$ we
have
\begin{equation} \label{P_repr}
P(n)=\sum_{d\mid n} d \, \phi(n/d),
\end{equation}
where $\phi$ is Euler's function.

Properties of the function $P$, which arise from the representation
\eqref{P_repr}, as well as various generalizations and analogs of it
were investigated by several authors. It is maybe not surprising
that some of these results were rediscovered for many times.

It follows from \eqref{P_repr} that the arithmetic mean of
$\gcd(1,n), \ldots, \gcd(n,n)$ is given by
\begin{equation} \label{P_arith_mean}
A(n)= \frac{P(n)}{n}= \sum_{d\mid n} \frac{\phi(d)}{d}.
\end{equation}

The harmonic mean of $\gcd(1,n), \ldots, \gcd(n,n)$ is
\begin{equation} \label{P_harm_mean}
H(n)= n \left(\sum_{k=1}^n \frac1{\gcd(k,n)} \right)^{-1} = n^2
\left(\sum_{d\mid n} d\, \phi(d)\right)^{-1}.
\end{equation}

In the present paper we give a survey of the gcd-sum function and of
its analogs. We also prove the following results concerning the
functions $A$ and $H$, which seem to have not appeared in the
literature.

Our first result is an asymptotic formula with remainder term for
the quadratic moment of the function $A$.

Let $\tau(n)$ denote, as usual, the number of divisors of $n$. Let
$\alpha_4$ be the exponent appearing in the divisor problem for the
function $\tau_4(n)=\sum_{d_1d_2d_3d_4=n} 1$, that is
\begin{equation}
\sum_{n\le x} \tau_4(n)= x(K_1\log^3 x+ K_2\log^2 x+ K_3\log x+ K_4)
+{\cal O} (x^{\alpha_4+\varepsilon}),
\end{equation}
for any $\varepsilon>0$, where $K_1=1/6,K_2,K_3,K_4$ are constants.
It is known that $\alpha_4 \le 1/2$  (result of Hardy and Littlewood)
and it is conjectured that $\alpha_4 = 3/8$, cf. Titchmarsh \cite[Ch.\
12]{Tit1986}, Ivi\'c et al. \cite[Section 4]{Ivi2006}. If this
conjecture were true, then it would follow that $\alpha_4 < 1/2$.

\begin{thm} \label{theorem 1} i) For any $\varepsilon>0$,
\begin{equation} \label{A^2_asymp}
\sum_{n\le x} A^2(n) = x(C_1\log^3 x+ C_2\log^2 x+ C_3\log x+ C_4)
+{\cal O} (x^{1/2+\varepsilon}),
\end{equation}
where $C_1,C_2,C_3,C_4$ are constants,
\begin{equation}
C_1=\frac1{\pi^2} \prod_p \left(1+\frac1{p^3}-\frac{4}{p(p+1)}
\right),
\end{equation}
$C_2,C_3,C_4$ are given by \eqref{const_Th1} in terms of the
constants appearing in the asymptotic formula for $\sum_{n\le x}
\tau^2(n)$.

ii) Assume that $\alpha_4<1/2$. Then the error term in
\eqref{A^2_asymp} is ${\cal O}(x^{1/2}\delta(x))$, where
\begin{equation} \label{error_delta}
\delta(x)=\exp(-c(\log x)^{3/5}(\log \log x)^{-1/5}),
\end{equation}
with a positive constant $c$.

iii) If the Riemann hypothesis (RH) is true, then for any real $x$
sufficiently large the error term in \eqref{A^2_asymp} is ${\cal
O}(x^{(2-\alpha_4)/(5-4\alpha_4)}\eta(x))$, where
\begin{equation} \label{error_omega}
\eta(x)=\exp((\log x)^{1/2}(\log \log x)^{14}).
\end{equation}
\end{thm}

\begin{rem} {\rm Let $M(x)=\sum_{n\le x} \mu(n)$ denote the Mertens
function,  where $\mu$ is the M\"obius function. The error term of
iii) comes from the estimate $M(x)\ll \sqrt{x}\, \eta(x)$, the best
up to now, valid under RH and for $x$ large, due to Soundararajan
\cite{Sou2009}. Note that in a preprint not yet published Balazard
and Roton \cite{BalRot2008} have shown that the slightly better
estimate $M(x)\ll \sqrt{x} \exp((\log x)^{1/2}(\log \log
x)^{5/2+\varepsilon})$ holds assuming RH, for every $\varepsilon >0$
sufficiently small.}
\end{rem}

\begin{rem} {\rm If $\alpha_4$ is near $3/8$ and RH is true, then the
exponent $(2-\alpha_4)/(5-4\alpha_4)$ is near $13/28\approx
0.4642$.}
\end{rem}

Our second result is regarding the function $H$.

\begin{thm} \label{theorem 2} For any $\varepsilon >0$,
\begin{equation}
\sum_{n\le x} \frac{H(n)}{n}= C_5\log x + C_6 + {\cal O}
\left(x^{-1+\varepsilon} \right),
\end{equation}
where $C_5$ and $C_6$ are constants,
\begin{equation}
C_5=\frac{\zeta(2)\zeta(3)}{\zeta(6)} \prod_p
\left(1-\frac{p-1}{p^2-p+1}\sum_{a=1}^{\infty}
\frac{p^{2a-1}+1}{p^{a-1}(p^{2a+1}+1)} \right).
\end{equation}
\end{thm}

\begin{cor} \label{corollary 1} For any $\varepsilon >0$,
\begin{equation}
\sum_{n\le x} H(n) = C_5 x + {\cal O} (x^{\varepsilon}),
\end{equation}
hence the mean value of the function $H$ is $C_5$.
\end{cor}

Note that the arithmetic mean of the orders of elements in the
cyclic group $C_n$ of order $n$ is
\begin{equation}
\alpha(n)= \frac1{n}\sum_{k=1}^n \frac{n}{\gcd(k,n)}= \frac1{n}
\sum_{d\mid n} d\phi(d),
\end{equation}
hence $H(n)/n=1/\alpha(n)$. The function $\alpha$ and its average
order were investigated by von zur Gathen et al. \cite{zGat2004} and
Bordell\`{e}s \cite{Bor2007b}.

The paper is organized as follows. Properties of the gcd-sum
function $P$ are presented in Section \ref{section 2}. Generalizations and
connections to other functions are given in Section \ref{section 3}. Section \ref{section 4}
includes the proofs of Theorems \ref{theorem 1} and \ref{theorem 2}. Several analogs of the
gcd-sum function are surveyed in Section \ref{section 5} and certain open problems
are stated in Section \ref{section 6}. Finally, as added in proof, asymptotic
formulae for $\sum_{n\le x} 1/P(n)$ and $\sum_{n\le x} 1/g(n)$,
where $g$ is any multiplicative analog of $P$ discussed in the
present paper are given in Section \ref{section 7}.

Throughout the paper we insist on the asymptotic properties of the
functions. We remark that some other aspects, including arithmetical
properties and generalizations of the gcd-sum function are surveyed
by Bege \cite[Ch.\ 3]{Beg2006} and Haukkanen \cite{Hau2008}.


%************************* Section 2 *******************************************

\section{Properties of the gcd-sum function} \label{section 2}

According to \eqref{P_repr}, $P=E*\phi$ in terms of the Dirichlet
convolution, with the notation $E(n)=n$. It follows that $P$ is
multiplicative and for any prime power $p^a$ ($a\ge 1$),
\begin{equation} \label{prime_pow}
P(p^a)=(a+1)p^a - ap^{a-1},
\end{equation}
in particular $P(p)=2p-1$, $P(p^2)=3p^2-2p$, etc.

$(P(n))_{n\ge 1}$ is sequence \seqnum{A018804} in Sloane's
Encyclopedia. It is noted there that $P(n)$ is the number of times
the number $1$ appears in the character table of the cyclic group
$C_n$. Also, $P(n)$ is the number of incongruent solutions of the
congruence $xy \equiv 0$ (mod $n$).

The bounds $2n-1\le P(n)\le n\tau(n)$ ($n\ge 1$) follow at once by
the definition \eqref{P_def} and \eqref{prime_pow}, respectively.
The Dirichlet series of $P$ is given by
\begin{equation} \label{P_Dirichlet}
\sum_{n=1}^{\infty} \frac{P(n)}{n^s}= \frac{\zeta^2(s-1)}{\zeta(s)}
\quad (\Re s>2).
\end{equation}

The convolution method applied for \eqref{P_repr} leads to the asymptotic formulae
\begin{equation} \label{P_asymptotic}
\sum_{n\le x} P(n)=\frac1{2\zeta(2)} x^2\log x + {\cal O}(x^2),
\end{equation}
\begin{equation} \label{P_asymptotic_mean}
\sum_{n\le x} \frac{P(n)}{n} = \frac1{\zeta(2)} x \log x + {\cal
O}(x).
\end{equation}

It follows that the average order of $A(n)=P(n)/n$ is $\log
n/\zeta(2)$, that is, for $1\le k \le n$ the average value of
$(k,n)$ is $\log n/\zeta(2)$, where $1/\zeta(2)=6/\pi^2 \approx
0.607927$.

\vskip1mm Figure 1 is a plot of the function $A(n)$  for $1\le n\le
10\, 000$, produced using Maple.

\begin{center}
\mapleplot{Pillai_plot02.eps}
\end{center}

Observe that writing $\phi = E*\mu$, by \eqref{P_repr} we have
$P=E*E*\mu= E\tau * \mu$, that is
\begin{equation} \label{P_repr_2}
P(n)=\sum_{d\mid n} d \tau(d)\mu(n/d).
\end{equation}

This follows also from \eqref{P_Dirichlet}. Note that $P$ is a
rational arithmetical function of order $(2,1)$, in the sense that
$P$ is the convolution of two completely multiplicative functions
and of another one which is the inverse (under convolution) of a
completely multiplicative function, cf. Haukkanen \cite{Hau1999}.

Using the representation \eqref{P_repr_2} the following more precise
asymptotic formula can be derived: for every $\varepsilon >0$,
\begin{equation} \label{P_asymptotic_precise}
\sum_{n\le x} P(n)=\frac{x^2}{2\zeta(2)}\left(\log x
+2\gamma-\frac1{2}-\frac{\zeta'(2)}{\zeta(2)}\right) + {\cal
O}(x^{1+\theta+\varepsilon}),
\end{equation}
where $\gamma$ is Euler's constant and $\theta$ is the number
appearing in Dirichlet's divisor problem, that is
\begin{equation} \label{Dirichlet_divisor}
\sum_{n\le x} \tau(n)= x\log x+(2\gamma-1)x+{\cal
O}(x^{\theta+\varepsilon}).
\end{equation}

It is known that $1/4\le \theta \le 131/416 \approx 0.3149$, where
the upper bound, the best up to date, is the result of Huxley
\cite{Hux2003}. To be more precise, the result of Huxley
\cite{Hux2003} says that the error term in \eqref{Dirichlet_divisor}
is
\begin{equation} \label{Huxley}
{\cal O}(x^{131/416} (\log x)^{26947/8320})
\end{equation}
with $26947/8320\approx 3.2388$.

The study of the gcd-sum function $P$ and of its generalization
$P_f$ given by \eqref{P_f} goes back to the work of Ces\`{a}ro in the years 1880'.
%end of the 19th century).
The formula
\begin{equation}
\sum_{k=1}^n f(\gcd(k,n)) =\sum_{d\mid n} f(d)\phi(n/d),
\end{equation}
valid for an arbitrary arithmetical function $f$, is sometimes referred to as Ces\`{a}ro's formula, cf.
Dickson \cite[p.\ 127, 293]{Dic1952}, S\'andor and Crstici \cite[p.\ 182]{SanCrs2004},
Haukkanen \cite{Hau2008}.

The function $P$ was rediscovered by Pillai \cite{Pil1933} in 1933,
showing formula \eqref{P_repr} and that
\begin{equation}
\sum_{d\mid n} P(d)= n\tau(n)=\sum_{d\mid n} \sigma(d)\phi(n/d),
\end{equation}
$\sigma(n)$ denoting, as usual, the sum of divisors of $n$.

Properties of $P$, including \eqref{P_repr}, \eqref{P_Dirichlet}
\eqref{P_asymptotic}, \eqref{P_asymptotic_mean} were discussed by
Broughan \cite{Bro2001} without referring to the work of Ces\`{a}ro
and Pillai.

Formulae \eqref{P_repr_2} and \eqref{P_asymptotic_precise} were
obtained, even for a more general function, by Chi\-dam\-ba\-ras\-wa\-my and
Sitaramachandrarao \cite{ChiSit1985}. They also proved the following result
concerning the maximal order of $P(n)$:
\begin{equation} \label{P_maximal}
\limsup_{n\to \infty} \frac{\log(P(n)/n) \log \log n}{\log n}= \log
2,
\end{equation}
which is well known for the function $\tau(n)$ instead of $P(n)/n$.
\eqref{P_repr_2} and \eqref{P_asymptotic_precise} were obtained
later also by Bordell\`{e}s \cite{Bor2007a}.

In a recent paper Bordell\`{e}s \cite[Th.\ 8, eq.\ (xi)]{Bor2010}
pointed out that, according to \eqref{Huxley}, the error term of
\eqref{P_asymptotic_precise} is ${\cal O}(x^{547/416}(\log
x)^{26947/8320})$.

The asymptotic formula \eqref{P_asymptotic_precise} was obtained
earlier by Kopetzky \cite{Kop1977} with a weaker error term. The
same formula \eqref{P_asymptotic_precise} was derived also by
Broughan \cite[Th.\ 4.7]{Bro2001} with the weaker error term ${\cal
O}(x^{3/2}\log x)$, but the coefficient of $x^2$ is not correct
($\zeta^2(2)/2\zeta(3)$ is given).

One has
\begin{equation} \label{Diaconis_Erdos}
\sum_{m,n\le x} \gcd(m,n)=\frac1{\zeta(2)}x^2\log x+ c x^2+ {\cal
O}(x^{1+\theta+\varepsilon}),
\end{equation}
with a suitable constant $c$, which follows from
\eqref{P_asymptotic_precise} using the connection formula between
the two types of summation, namely $\sum_{n\le x} P(n)=\sum_{m\le
n\le x} \gcd(m,n)$ and $\sum_{m,n\le x} \gcd(m,n)$, cf. Section \ref{section 3}.
Formula \eqref{Diaconis_Erdos} was given by Diaconis and Erd\H os
\cite{DiaErd2004} with the weaker error term ${\cal O}(x^{3/2}\log
x)$.

The study of asymptotic formulae with error terms of $\sum_{n\le x}
P(n)/n^s$ for real values of $s$ was initiated by Broughan
\cite{Bro2001, Bro2007} and continued by Tanigawa and Zhai
\cite{TanZha2008}.

Alladi \cite{All1975} gave asymptotic formulae for $\sum_{k=1}^n
(\gcd(k,n))^s$ and $\sum_{k=1}^n (\lcm[k,n])^s$ ($s\ge 1$). Sum
functions of the gcd's and lcm's were also considered by Gould and
Shonhiwa \cite{GouSho1997,ShoGou1997} and Bordell\`{e}s
\cite{Bor2007b}.

The function $P$ appears in the number theory books of Andrews
\cite[p.\ 91, Problem 10]{And1971}, Niven and Zuckerman
\cite[Section 4.4, Problem 6]{NivZuc1972} (the author of this survey
met the function $P$ for the first time in the Hungarian translation
of this book) and McCarthy \cite[p.\ 29, Problem 1.3]{McC1986}.

See also the proposed problems of Shallit \cite{Sha1980} ($P$ is
multiplicative and \eqref{prime_pow}), Teuffel \cite{Teu1970}
(formulae \eqref{P_repr}, \eqref{P_asymptotic} and asymptotic
formulae for $\sum_{k=1}^n (\gcd(k,n))^s$ with $s\ge 2$) and Lau
\cite{Lau1989} (asymptotic formulae for $\sum_{1\le i,j\le n}
\gcd(i,j)$ and $\sum_{1\le i,j\le n} \lcm[i,j]$).

In a recent paper de Koninck and K\'atai \cite{KonKat2010} investigated
two general classes of functions, one of them including
$A(n)=P(n)/n$, and showed that
\begin{equation} \label{Katai_estimate}
\sum_{p\le x} A(p-1)  = L x + {\cal O}(x(\log \log x)^{-1}),
\end{equation}
where the sum is over the primes $p\le x$ and $L$ is a constant
given by
\begin{equation}
L=\frac1{2}\prod_p \left(1+\frac1{p(p-1)}\right) \sum_{n=1}^{\infty}
\frac{F(n)\tau(n)}{n}\prod_{p\mid n}
\left(1+\frac{p}{(p-1)^2}\right)^{-1},
\end{equation}
where $F$ is the multiplicative function defined by
$F(p^a)=-\frac{a/(a+1)}{p}$ for any prime power $p^a$ ($a\ge 1$).


%************************* Section 3 *******************************************

\section{Generalizations, connections to other functions} \label{section 3}

The gcd-sum function $P$ can be generalized in various directions.
For example:

i) One can investigate the function
\begin{equation} \label{P_s}
P_s(n)=\sum_{k=1}^n (\gcd(k,n))^s,
\end{equation}
where $s$ is a real number. More generally, for an arbitrary
arithmetical function $f$ let
\begin{equation} \label{P_f}
P_f(n)=\sum_{k=1}^n f(\gcd(k,n)),
\end{equation}
mentioned already in Section \ref{section 2}.

ii) A multidimensional version is the function
\begin{equation} \label{P_k}
P_{(k)}(n)=\sum_{1\le i_1,\ldots,i_k\le n} \gcd(i_1,\ldots,i_k,n).
\end{equation}

iii) If $g$ is a nonconstant polynomial with integer coefficients
let
\begin{equation} \label{P_g}
P^{(g)}(n)=\sum_{k=1}^n \gcd(g(k),n).
\end{equation}

iv) If $A$ is a regular convolution and $(k,n)_A$ is the greatest
divisor $d$ of $k$ such that $d\in A(n)$ (see for ex. McCarthy
\cite[Ch.\ 4]{McC1986}) let
\begin{equation} \label{P_A}
P_A(n)=\sum_{k=1}^n (k,n)_A.
\end{equation}

These generalizations can also be combined. The general function
investigated by T\'oth \cite{Tot1998} includes all of i)-iv) given
above (it is even more general). T\'oth \cite{Tot1990} considered a
generalization defined for arithmetical progressions. We do not deal
here with these generalizations, see
\cite{Beg2006,ChiSit1985,Hau2008, Kop1977,Siv1971,Vas1966}, but
point out the following properties concerning functions of type
$P_f$ given by \eqref{P_f}.

For an arbitrary arithmetical function $f$,
\begin{equation}
S_f(x)= \sum_{m,n\le x} f(\gcd(m,n))= 2\sum_{n\le x} \sum_{k=1}^n
f(\gcd(k,n)) -\sum_{n\le x} f(n)
\end{equation}
\begin{equation*}
 = 2\sum_{n\le x} P_f(n) -\sum_{n\le x} f(n),
\end{equation*}
cf. Cohen \cite[Lemma 3.1]{Coh1960i}. In that paper asymptotic
formulae for $S_f(x)$ are deduced if $f(n)=\sum_{de=n} g(d)e^t$,
where $t\ge 1$ and $g$ is a bounded arithmetical function. For
example, Cohen \cite[Cor.\ 3.2]{Coh1960i} derived that
\begin{equation} \label{Cohen_phi}
\sum_{m,n\le x} \phi(\gcd(m,n)) = \frac{x^2}{\zeta^2(2)}\left( \log
x + 2\gamma -\frac1{2} -\frac{\zeta(2)}{2}-
\frac{2\zeta'(2)}{\zeta(2)}\right)+ R(x),
\end{equation}
where $R(x)={\cal O}(x^{3/2}\log x)$ and a similar result with the
same error term for the function $\sigma(n)$. Cohen \cite{Coh1962ii}
improved these error terms into $R(x)={\cal O}(x^{3/2})$ by an
elementary method.

For $f=g*E$ one has $P_f=(g*\mu)*E\tau$, and simple convolution
arguments show that for $g$ bounded the error term for $\sum_{n\le
x} P_f(n)$ is the same as in \eqref{P_asymptotic_precise} and in
\eqref{Cohen_phi}, namely ${\cal O}(x^{1+\theta+\varepsilon})$. This
was obtained also by Cohen \cite{Coh1961iii}, in a slightly
different form.

Similar asymptotic formulae can be given for other choices of $f$. For example, let $f=\mu^2$.
Then $P_{\mu^2}(p)= p$, $P_{\mu^2}(p^a)=p^a-p^{a-2}$ for any prime $p$ and any $a\ge 2$.
Furthermore, $P_{\mu^2}(n)=\sum_{d^2e=n} \mu(d)e$ and obtain
\begin{equation} \label{P_mu^2}
\sum_{n\le x} P_{\mu^2}(n)= \frac{x^2}{2\zeta(4)} + {\cal O}(x).
\end{equation}

Bordell\`{e}s \cite[Th.\ 4]{Bor2010} provides some general
asymptotic results for $\sum_{n\le x} P_f(n)$ with $f$ belonging to
certain classes of arithmetic functions. As special cases and among
others, the following estimates are proven (\cite[Th.\ 8, eq.
(i),(ii),(iii),(v)]{Bor2010}):
\begin{equation} \label{P_mu_k}
\sum_{n\le x} P_{\mu_k}(n)= \frac{x^2}{2\zeta(2k)} + {\cal O}(x),
\end{equation}
\begin{equation} \label{P_tau_(k)}
\sum_{n\le x} P_{\tau_{(k)}}(n)= \frac{\zeta(2)}{2\zeta(2k)}x^2 +
{\cal O}(x(\log x)^{2/3}),
\end{equation}
\begin{equation} \label{P_beta}
\sum_{n\le x} P_{\beta}(n)= \frac{\zeta(4)\zeta(6)}{2\zeta(12)} x^2
+ {\cal O}(x),
\end{equation}
\begin{equation} \label{P_abel}
\sum_{n\le x} P_a(n)= \frac{x^2}{2}\prod_{j =2}^{\infty} \zeta(2j) +
{\cal O}(x),
\end{equation}
where $\mu_k$ is the characteristic function of the $k$-free
integers, $\tau_{(k)}(n)$ is the number of $k$-free divisors of $n$
($k \ge 2$), $\beta(n)$ is the number of squarefull divisors of $n$
and $a(n)$ represents the number of non-isomorphic abelian groups of
order $n$. For $k=2$, \eqref{P_mu_k} gives \eqref{P_mu^2}.

Note that certain error terms given by Bordell\`{e}s \cite[Th.\
8]{Bor2010} can be improved. For example, the error term of
\eqref{P_tau_(k)} is given in \cite{Bor2010} with an extra factor
$(\log \log x)^{4/3}$. Here \eqref{P_tau_(k)} yields by observing
that $P_{\tau_{(k)}}(n)=\sum_{d^ke=n} \mu(d)\sigma(e)$ and using the
following estimate of Walfisz: $\sum_{n\le x}
\sigma(n)=\frac{\zeta(2)}{2}x^2+{\cal O}(x(\log x)^{2/3})$.

We have $\sum_{k=1}^n a^{\gcd(k,n)}=\sum_{d\mid n} a^d\phi(n/d)
\equiv 0$ (mod $n$) for any integers $a,n\ge 1$. This known
congruence property has number theoretical and combinatorial proofs
and interpretations, cf. Dickson \cite[p.\ 78, 86]{Dic1952}.

The related formula
\begin{equation}
\sum_{\substack{k=1\\ \gcd(k,n)=1}}^n \gcd(k-1,n)= \tau(n) \phi(n)
\quad (n\ge 1)
\end{equation}
is due to Kesava Menon \cite{Kes1965}. See also McCarthy \cite[Ch.\ 1]{McC1986}.

The products
\begin{equation}
h(n)=\prod_{k=1}^n \gcd(k,n), \quad h_f(n)=\prod_{k=1}^n
f(\gcd(k,n))
\end{equation}
were considered by Loveless \cite{Lov2006} (\seqnum{A067911}). Note
that the geometric mean of $\gcd(1,n)$, $\ldots$, $\gcd(n,n)$ is
$G(n)=(h(n))^{1/n}= n /\prod_{d\mid n} d^{\phi(d)}$, which is a
multiplicative function of $n$, cf. \cite[Th.\ 6]{Lov2006}.

Using that $\log h(n) = \sum_{d\mid n} \phi(n/d)\log d $ we deduce
\begin{equation} \label{Prod_estimate}
\sum_{n\le x} \log h(n) = -\frac{\zeta'(2)}{2\zeta(2)}x^2+{\cal
O}(x(\log x)^{8/3} (\log \log x)^{4/3})
\end{equation}
by applying the estimate of Walfisz for $\phi$, namely
\begin{equation} \label{Walfisz}
\sum_{n\le x} \phi(n) = \frac1{2\zeta(2)}x^2+ {\cal O}(x(\log
x)^{2/3} (\log \log x)^{4/3}),
\end{equation}
providing the best error up to date.  \eqref{Prod_estimate} is given
by Loveless \cite[Th.\ 11, Corrig.]{Lov2006} with a weaker error
term, namely with ${\cal O}(x\log^3 x)$.

Some authors, including Diaconis and Erd\H os \cite{DiaErd2004},
Bege \cite{Beg2006}, Broughan \cite{Bro2001} use or refer to a
result of Saltykov -- the error term in \eqref{Walfisz} is ${\cal
O}(x(\log x)^{2/3} (\log \log x)^{1+\varepsilon})$ -- which is not
correct(!) as it was shown by P\'etermann \cite{Pet1998}.

Note that Bordell\`{e}s  \cite{Bor2007b} obtained asymptotic
formulae for another type of generalization, namely given by
$g_k=\mu* E\tau_k$, where $\tau_k$ is the generalized
(Dirichlet-Piltz) divisor function. It is more natural to define
such functions $P^{(k)}$ in this way: $P^{(1)}(n)=P(n)$,
$P^{(k+1)}(n)= \sum_{j=1}^n P^{(k)}(\gcd(j,n))$ ($k\ge 1$). Then
$P^{(k)}= \underbrace{\mu*\cdots *\mu}_k* E\tau_k$ and asymptotic
formulae for $P^{(k)}$ can be given.

Let $n_1,\ldots, n_r$ be positive integers, where $r\ge 1$ and
$m=\lcm[n_1,\ldots,n_r]$. The multivariate function
\begin{equation} \label{P_multi}
P(n_1,\ldots,n_r)= \frac1{m} \sum_{k=1}^m \gcd(k,n_1)\cdots \gcd(k,n_r)
\end{equation}
was considered by Minami \cite{Min2009}. For $r=1$ this reduces to
$P$. One has, inserting $\gcd(k,n_i)=\sum_{d_i\mid \gcd(k,n_i)}
\phi(d_i)$,
\begin{equation}
P(n_1,\ldots,n_r)= \sum_{d_1\mid n_1, \ldots, d_r\mid n_r} \frac{\phi(d_1)\cdots
\phi(d_r)}{\lcm[d_1,\ldots, d_r]},
\end{equation}
formula not given in \cite{Min2009}.

Schramm \cite{Sch2008} investigated the discrete Fourier transform
of functions of the form $f(\gcd(n,r))$, where $f$ is an arbitrary
arithmetic function. He considered also various special functions
$f$ and deduced interesting identities, for example,
\begin{equation} \label{Sch_phi}
\phi(r)= \sum_{k=1}^r \gcd(k,r) \exp(-2\pi ik/r),
\end{equation}
\begin{equation} \label{Sch_gcd}
\gcd(n,r)= \sum_{k=1}^r  \exp(2\pi ikn/r)\sum_{d\mid r} c_d(k)/d,
\end{equation}
valid for $n,r\ge 1$, where $c_d(k)$ denotes the Ramanujan sum.

The function $\alpha$ (cf. \seqnum{A057660}) defined in the
Introduction was considered also by S\'andor and Kramer
\cite{SanKra1999}.


%************************* Section 4 *******************************************
\section{Proofs of Theorems \ref{theorem 1} and \ref{theorem 2}} \label{section 4}

{\bf Proof of Theorem \ref{theorem 1}.} i) First we show that
\begin{equation} \label{quadratic_convo}
A^2(n) = \sum_{de=n} \tau^2(d)g(e),
\end{equation}
where $g$ is multiplicative and $g(p)=-4/p+1/p^2$, $g(p^a)=4(-1)^a/p$ for
any prime $p$ and $a\ge 2$.

By the multiplicativity of the involved functions it is enough to
verify \eqref{quadratic_convo} for prime powers $p^a$ ($a\ge 1$). We
have
\begin{equation*}
\sum_{de=p^a} \tau^2(d)g(e)= \sum_{j=1}^{a-1} \tau^2(p^{j-1}) g(p^{a-j+1})+\tau^2(p^{a-1})g(p)+\tau^2(p^a)
\end{equation*}
\begin{equation*}
= \sum_{j=1}^{a-1} j^2 (-1)^{a-j+1}\frac{4}{p} +a^2(-4/p+1/p^2)+(a+1)^2
\end{equation*}
\begin{equation*}
=(-1)^a\frac{4}{p}\sum_{j=1}^{a-1} (-1)^{j-1}j^2 + \frac{a^2}{p^2} -
\frac{4a^2}{p} +(a+1)^2 = (a+1-a/p)^2= A^2(p^a),
\end{equation*}
which follows by the elementary formula
\begin{equation*}
\sum_{j=1}^n (-1)^{j-1} j^2 = (-1)^{n-1} \frac{n(n+1)}{2} \quad (n\ge 1).
\end{equation*}

Here the Dirichlet series of $g$ is given by
\begin{equation*}
G(s)= \sum_{n=1}^{\infty} \frac{g(n)}{n^s}= \prod_p
\left(1+\frac1{p^{s+2}}-\frac{4}{p(p^s+1)}\right),
\end{equation*}
which is absolutely convergent for $s\in \C$ with $\Re s>0$.
Therefore, for any $\varepsilon >0$,
\begin{equation*}
\sum_{n\le x} g(n) ={\cal O}(x^{\varepsilon}), \quad \sum_{n>x}
\frac{g(n)}{n} = {\cal O}(x^{-1+\varepsilon}).
\end{equation*}

We need the next formula of Ramanujan, cf. Wilson \cite{Wil1922},
\begin{equation} \label{Ramanujan}
\sum_{n\le x} \tau^2(n) = x(a\log^3 x+ b\log^2 x+ c\log x+ d) +
{\cal O} (x^{1/2+\varepsilon}),
\end{equation}
where $a=1/\pi^2,b,c,d$ are constants.

By \eqref{quadratic_convo} and \eqref{Ramanujan} we obtain
\begin{equation*}
\sum_{n\le x} A^2(n) = \sum_{d\le x} g(d)\sum_{e\le x/d} \tau^2(e)
\end{equation*}
\begin{equation*}
= ax \sum_{d\le x} \frac{g(d)}{d} \log^3(x/d) + bx \sum_{d\le x}
\frac{g(d)}{d} \log^2(x/d) + cx \sum_{d\le x} \frac{g(d)}{d}
\log(x/d) + dx \sum_{d\le x} \frac{g(d)}{d}
\end{equation*}
\begin{equation*}
+ {\cal O}\left(x^{1/2+\varepsilon} \sum_{d\le x}
\frac{|g(d)|}{d^{1/2+\varepsilon}} \right).
\end{equation*}

Now formula \eqref{A^2_asymp} follows by usual estimates with the
constants
\begin{equation} \label{const_Th1}
C_1=aG(1), \quad C_2=3aG'(1)+bG(1), \quad
C_3=3aG''(1)+2bG'(1)+cG(1),
\end{equation}
\begin{equation*}
C_4=aG'''(1)+bG''(1)+cG'(1)+ d G(1),
\end{equation*}
where $G', G'', G'''$ are the derivatives of $G$.

ii) Assume that $\alpha_4 <1/2$. We use that in this case the error
term for $\sum_{n\le x} \tau^2(n)$ in \eqref{Ramanujan} is ${\cal O}
(x^{1/2}\delta(x))$, as it was proved by Suryanarayana and
Sitaramachandra Rao \cite{SurSit1973}. We obtain, applying that
$x^{\varepsilon}\delta(x)$ is increasing, that the error term for
$\sum_{n\le x} A^2(n)$ is
\begin{equation*}
\ll \sum_{d\le x} |g(d)| (x/d)^{1/2}\delta(x/d) = \sum_{d\le x}
|g(d)| (x/d)^{1/2-\varepsilon} (x/d)^{\varepsilon}\delta(x/d)
\end{equation*}
\begin{equation*}
\ll x^{1/2-\varepsilon} (x^{\varepsilon} \delta(x)) \sum_{d\le x}
\frac{|g(d)|}{d^{1/2-\varepsilon}}\ll x^{1/2}\delta(x).
\end{equation*}

iii) Assume RH. Then we apply that the error term of
\eqref{Ramanujan} is ${\cal O}
(x^{(2-\alpha_4)/(5-4\alpha_4)}\eta(x))$, cf. \cite[Lemma 2.4, Th.\
3.2]{SurSit1973}, where $\sum_{n\le x} \mu(n) \ll x^{1/2}\eta(x)$
according to the result of Soundararajan \cite{Sou2009} quoted in
the Introduction. Using that $\eta(x)$ is increasing, we obtain the
given error term.

\vskip1mm {\bf Proof of Theorem \ref{theorem 2}.} The function $H$ is
multiplicative and for any prime power $p^a$ ($a\ge 1$),
\begin{equation} H(p^a)= \frac{p^{2a}(p+1)}{p^{2a+1}+1}.
\end{equation}

Now write
\begin{equation*}
\frac{H(n)}{n} = \sum_{\substack{de=n\\(d,e)=1}}
\frac{h(d)}{\phi(e)}
\end{equation*}
as the unitary convolution of the functions $h$ and $1/\phi$, where
$h$ is multiplicative and for every prime power $p^a$ ($a \ge 1$),
\begin{equation*}
\frac{H(p^a)}{p^a}= h(p^a)+ \frac1{\phi(p^a)}, \quad h(p^a)= -
\frac{p^{2a-1}+1}{p^{a-1}(p-1)(p^{2a+1}+1)},
\end{equation*}
where
\begin{equation*}
|h(p^a)|< \frac1{p^a(p-1)^2}, \quad |h(n)|\le \frac{f(n)}{\phi(n)} \
(n\ge 1),
\end{equation*}
with $f(n)=\prod_{p\mid n} (p(p-1))^{-1}$.

We need the following known result, cf. for example Montgomery and
Vaughan \cite[p.\ 43]{MonVau2007},
\[
\sum_{\substack{n\le x\\ (n,k)=1}} \frac1{\phi(n)} = K a(k)
\left(\log x + \gamma + b(k)\right)+ {\cal O} \left(2^{\omega(k)}
\frac{\log x}{x}\right),
\]
where $\gamma$ is Euler's constant, $\omega(k)$ stands for the
number of distinct prime divisors of $k$,
\[
K= \frac{\zeta(2)\zeta(3)}{\zeta(6)}, \ a(k)=\prod_{p\mid
k}\left(1-\frac{p}{p^2-p+1}\right) \le \frac{\phi(k)}{k}, \]
\[
b(k)=\sum_{p\mid k} \frac{\log p}{p-1}- \sum_{p\nmid k} \frac{\log
p}{p^2-p+1} \ll \frac{\psi(k)\log k}{\phi(k)}, \ \text{ with } \
\psi(k)= k \prod_{p\mid k} \left(1+\frac1{p}\right).
\]

We obtain
\[
\sum_{n\le x} \frac{H(n)}{n} = \sum_{d\le x} h(d)
\sum_{\substack{e\le x/d\\ \gcd(e,d)=1}} \frac1{\phi(e)}=
\]
\[
= K \left((\log x+\gamma)\sum_{d\le x} h(d)a(d)+\sum_{d\le x}
h(d)a(d)(b(d)-\log d) \right)+O\left(\frac{\log x}{x}\sum_{d\le x} d
|h(d)|2^{\omega(d)} \right),
\]
and we obtain the given result with the constants
\[
C_5= K\sum_{n=1}^{\infty} h(n)a(n), \ C_6 =K\gamma
\sum_{n=1}^{\infty} h(n)a(n) + K \sum_{n=1}^{\infty}
h(n)a(n)(b(n)-\log n),
\]
these series being convergent taking into account the estimates of
above. For the error terms,
\[
\sum_{n>x} |h(n)|a(n) \le \sum_{n>x} \frac{f(n)}{n} < \sum_{n>x}
\frac{f(n)}{n} (\frac{n}{x})^{1-\varepsilon} < x^{-1+\varepsilon}
\sum_{n=1}^{\infty} \frac{f(n)}{n^{\varepsilon}}
\]
\[
=x^{-1+\varepsilon} \prod_p \left(1+\frac1{p(p-1)
(p^{\varepsilon}-1)}\right)\ll x^{-1+\varepsilon},
\]
in a similar way,
\[
\sum_{n>x} a(n)|h(n)(b(n)-\log n)| \ll x^{-1+\varepsilon},
\] and
\[
\sum_{n\le x} n |h(n)|2^{\omega(n)}\le \sum_{n\le x} (\prod_{p\mid
n} 1/(p-1)^2) 2^{\omega(n)} (\frac{x}{n})^{\varepsilon} <
x^{\varepsilon} \sum_{n=1}^{\infty}
\frac{2^{\omega(n)}}{n^{\varepsilon}} (\prod_{p\mid n} 1/(p-1)^2)
\]
\[
=x^{\varepsilon} \prod_p \left(1+\frac{2}{(p-1)^2
(p^{\varepsilon}-1)}\right)\ll x^{\varepsilon},
\]
ending the proof, which is similar to that of T\'oth \cite[Th.\
6]{Tot2008}.

\vskip1mm {\bf Proof of Corollary \ref{corollary 1}.} Follows from Theorem \ref{theorem 2} by
partial summation.


%************************* Section 5 *******************************************
\section{Analogs of the gcd-sum function} \label{section 5}

\subsection{Unitary analog}

Recall, that a positive integer $d$ is said to be a unitary divisor
of $n$ if $d\mid n$ and $\gcd (d,n/d)=1$, notation $d \mid \mid n$.
The unitary analogue of the function $P$ is the function
\begin{equation} \label{P*}
P^*(n)=\sum_{k=1}^n (k,n)_*,
\end{equation}
where $(k,n)_*:=\max \{d\in \N: d\mid k, d\mid \mid n\}$, which was
introduced by T\'oth \cite{Tot1989}. The function $P^*$
(\seqnum{A145388}) is also multiplicative and $P^*(p^a)=2p^a-1$ for
every prime power $p^a$ ($a\ge 1$). It has also other properties,
including asymptotic ones, which are close to the usual gcd-sum
function.

Consider the function $\phi^*$ (the unitary Euler function,
\seqnum{A047994}) defined by
\begin{equation} \label{phi*}
\phi^*(n)= \# \{k\in \N: 1\le k\le n, (k,n)_*=1\},
\end{equation}
which is multiplicative and $\phi^*(p^a)=p^a-1$ for every prime
power $p^a$ ($a\ge 1$). Then
\begin{equation}
P^*(n)=\sum_{d\mid \mid n} d \phi^*(n/d).
\end{equation}

It was proved by T\'oth \cite{Tot1996} that
\begin{equation} \label{asymptotic_P*}
\sum_{n\le x} P^*(n) = \frac{\alpha}{2\zeta(2)}x^2\log x + \beta
x^2+{\cal O}(x^{3/2}\log x),
\end{equation}
where $\alpha =\prod_p (1-1/(p+1)^2)\approx 0.775883$, cf. \cite[p.\
110]{Fin2003} and $\beta$ are constants.

Note that we also have
\begin{equation} \label{P^*_maximal}
\limsup_{n\to \infty} \frac{\log(P^*(n)/n) \log \log n}{\log n}=
\log 2,
\end{equation}
the same result as for $P(n)$. This is not given in the literature.
For the proof, which is similar to that of \cite[Th.\
1]{Tot2009reg}, take into account \eqref{P_maximal}, where the
limsup is attained for a sequence of square-free integers (more
exactly for $n_k= \prod_{k/\log^2 k<p\le k} p$, $k\to \infty$), see
\cite[Th.\ 4.1]{ChiSit1985}, and use that $P^*(n) \le P(n)$ for
every $n\ge 1$, with equality for any $n$ square-free.

\subsection{Bi-unitary analog}

Let $(k,n)_{**}= \max \{d\in \N: d\mid \mid k, d\mid \mid n\}$ stand
for the greatest common unitary divisor of $k$ and $n$ and
\begin{equation}
P^{**} (n)=\sum_{k=1}^n (k,n)_{**}
\end{equation}
be the bi-unitary gcd-sum function, introduced by Haukkanen
\cite{Hau2008}.

Haukkanen \cite[Cor.\ 3.1]{Hau2008} showed that
\begin{equation} \label{P**_formula}
P^{**} (n)= \sum_{d\mid \mid n} \phi^{*}(d)\phi(n/d,d),
\end{equation}
where $\phi(x,n)=\# \{k\in \N: 1\le k\le x, \gcd (k,n)=1\}$ is the
Legendre function.

Note that for every $n\ge 1$,
\begin{equation}
P^{**}(n)\le P^*(n)\le P(n).
\end{equation}

The function $P^{**}$ is not multiplicative and a combinatorial type formula for
$P^{**}(n)$ was given by T\'oth \cite{Tot2009bi}. In that paper it
was also proved, that
\begin{equation}
\sum_{n\le x} P^{**} (n)= \frac1{2} B x^2 \log x+ {\cal O}(x^2),
\end{equation}
where
\begin{equation}
B = \prod_p \left(1-\frac{3p-1}{p^2(p+1)}\right) = \zeta(2) \prod_p
\left(1-\frac{(2p-1)^2}{p^4}\right).
\end{equation}

\subsection{Analog involving exponential divisors}

The next analog is concerning exponential divisors. Let $n>1$ be an
integer of canonical form $n=\prod_{i=1}^r p_i^{a_i}$. The integer
$d$ is called an exponential divisor of $n$ if $d=\prod_{i=1}^r
p_i^{c_i}$, where $c_i \mid a_i$ for every $1\le i \le r$, notation:
$d\mid_e n$. By convention $1\mid_e 1$. Note that $1$ is not an
exponential divisor of $n>1$, the smallest exponential divisor of
$n>1$ is its square-free kernel $\kappa(n)=\prod_{i=1}^r p_i$.

Two integers $n,m >1$ have common exponential divisors iff they have
the same prime factors and in this case, i.e., for $n=\prod_{i=1}^r
p_i^{a_i}$, $m=\prod_{i=1}^r p_i^{b_i}$, $a_i,b_i\ge 1$ ($1\le i\le
r$), the greatest common exponential divisor of $n$ and $m$ is
\begin{equation}
(n,m)_{(e)}=\prod_{i=1}^r p_i^{(a_i,b_i)}.
\end{equation}

Here $(1,1)_{(e)}=1$ by convention and $(1,m)_{(e)}$ does not exist
for $m>1$.

Let $P^{(e)}(n)$ be given by
\begin{equation}
P^{(e)}(n)=\sum_{\substack{1\le k\le n \\ \kappa(k)=\kappa(n)}}
(k,n)_{(e)},
\end{equation}
introduced by T\'oth \cite{Tot2004}. The function $P^{(e)}$ is
multiplicative and for every prime power $p^a$,
\begin{equation}
P^{(e)}(p^a) = \sum_{1\le j\le a} p^{(j,a)}= \sum_{d \mid a} p^d
\phi(a/d),
\end{equation}
here $P^{(e)}(p)=p$, $P^{(e)}(p^2)=p+p^2$, $P^{(e)}(p^3)=2p+p^3$,
$P^{(e)}(p^4)=2p+p^2+p^4$, etc.

We have, see \cite[Th.\ 3]{Tot2004},
\begin{equation} \label{P_exp}
\sum_{n\le x} P^{(e)}(n) = E x^2 + {\cal O}(x (\log x)^{5/3}),
\end{equation}
where the constant $E$ is given by
\begin{equation}
E=\frac1{2} \prod_p \left(1+ \sum_{a=2}^{\infty}
\frac{P^{(e)}(p^a)-p P^{(e)}(p^{a-1})}{p^{2a}}\right).
\end{equation}

P\'etermann \cite[Th.\ 2]{Pet} showed that for $s\in \C$, $\Re s
>2$,
\begin{equation} \label{P_exp_Dirichlet}
\sum_{n=1}^{\infty} \frac{P^{(e)}(n)}{n^s} =
\frac{\zeta(s-1)\zeta(2s-1)}{\zeta(3s-2)}W(s),
\end{equation}
where $W(s)$ is absolutely convergent for $\Re s >3/4$ and that the
error term of \eqref{P_exp} is $\Omega_{\pm}(x\log \log x)$.

Concerning the maximal order of the function $P^{(e)}$ we have by
\cite[Th.\ 4]{Tot2004},
\begin{equation} \limsup_{n\to \infty} \frac{P^{(e)}(n)}{n\log\log n}
= \frac{6}{\pi^2}e^{\gamma},
\end{equation}
where $\gamma$ is Euler's constant.

\subsection{Analog involving regular integers (mod $n$)}

Next we give another analog. Let $n>1$ be an integer with prime
factorization $n=p_1^{\nu_1}\cdots p_r^{\nu_r}$. An integer $k$ is
called regular (mod $n$) if there exists an integer $x$ such that
$k^2x\equiv k$ (mod $n$). It can be shown that $k\ge 1$ is regular
(mod $n$) if and only if for every $i\in \{1,\ldots,r\}$ either
$p_i\nmid k$ or $p_i^{\nu_i}\mid k$. Also, $k\ge 1$ is regular (mod
$n$) if and only if $\gcd (k,n)$ is a unitary divisor of $n$. These
and other characterizations of regular integers are given by T\'oth
\cite{Tot2008}.

Let $\Reg_n=\{k: 1\le k\le n$ and $k$ is regular (mod $n$)$\}$.
T\'oth \cite{Tot2009reg} introduced the function
\begin{equation} \label{gcd-sum_regular}
\widetilde{P}(n)=\sum_{k\in \Reg_n} \gcd (k,n)
\end{equation} (\seqnum{A176345}) and showed the following properties. For every $n\ge 1$,
\begin{equation} \label{gcd-sum_regular_convo1}
\widetilde{P}(n)=\sum_{d\mid \mid n} d \, \phi(n/d),
\end{equation}
hence $\widetilde{P}$ is a multiplicative function and
\begin{equation} \label{gcd-sum_regular_expl}
\widetilde{P}(n)=n\prod_{p\mid n} \left(2-\frac1{p} \right).
\end{equation}

Also, the minimal order of $\widetilde{P}(n)$ is $3n/2$ and the
maximal order of $\log(\widetilde{P}(n)/n)$ is $\log 2 \log n/\log
\log n$. We have
\begin{equation} \label{P_reg}
\sum_{n\le x} \widetilde{P}(n) = \frac{x^2}{2\zeta(2)} (K_1\log x+
K_2) + {\cal O}(x^{3/2}\delta(x)),
\end{equation}
where $K_1$ and $K_2$ are certain constants and $\delta(x)$ is given
by \eqref{error_delta}.

If RH is true, then the error term of \eqref{P_reg} is ${\cal
O}(x^{(7-5\theta)/(5-4\theta)} \omega(x))$, where
\begin{equation}
\omega(x) =\exp(c\log x(\log \log x)^{-1})
\end{equation}
with a positive constant $c$ and $\theta$ the exponent in the
Dirichlet divisor problem \eqref{Dirichlet_divisor}. For $\theta
\approx 0.3149$ one has $(7-5\theta)/(5-4\theta)\approx 1.4505$.

Zhang and Zhai \cite{ZhaZha2010} showed that for $s\in \C$, $\Re s
>2$,
\begin{equation} \label{P_reg_Dirichlet}
\sum_{n=1}^{\infty} \frac{\widetilde{P}(n)}{n^s} =
\frac{\zeta^2(s-1)}{\zeta(2s-2)}H(s),
\end{equation}
where $H(s)=\prod_p \left(1-\frac1{p(p^{s-1}+1)}\right)$ is
absolutely convergent for $\Re s >1$, the error term of
\eqref{P_reg} is connected to the square-free divisor problem and it
is ${\cal O}(x^{15/11+\varepsilon})$, where $15/11\approx 1.3636$,
assuming RH.

De Koninck and K\'atai \cite{KonKat2010} showed that for
$\widetilde{A}(n)=\widetilde{P}(n)/n$,
\begin{equation} \label{Katai_estimate_2}
\sum_{p\le x} \widetilde{A}(p-1)  = L' x + {\cal O}(x(\log \log
x)^{-1}),
\end{equation}
where $L'$ is a constant, result which is similar to
\eqref{Katai_estimate}.

\vskip1mm Figure 2 is a plot of the function $\widetilde{A}(n)$  for
$1\le n\le 10\, 000$, produced using Maple.

\begin{center}
\mapleplot{plot_reg01.eps}
\end{center}

\subsection{Analog concerning subsets of the set $\{1,2,\ldots,n\}$}

For a nonempty subset $A$ of $\{1,2,\ldots, n\}$ let $\gcd(A)$
denote the gcd of the elements of $A$. Consider the gcd-sum type
functions $P_{\cal S}$ and $P_{{\cal S},k}$ defined by
\begin{equation}
P_{\cal S}(n)=\sum_{A} \gcd(\gcd(A),n)), \quad P_{{\cal S},k}(n)=
\sum_{\#A=k} \gcd(\gcd(A),n)),
\end{equation}
where the sums are over all nonempty subsets $A$ of $\{1,2,\ldots,
n\}$ and over all subsets $A$ of $\{1,2,\ldots, n\}$ having $k$
elements ($k\ge 1$ fixed), respectively. For $k=1$ this reduces to
the function $P$.

These are special cases of more general gcd-sum type functions
investigated by T\'oth \cite{Tot2010}. We have, cf. \cite[eq.\
(34),(37),(38)]{Tot2010},
\begin{equation}
P_{\cal S}(n)=\sum_{d\mid n} \phi(d)2^{n/d}-n  \quad (n\ge 1),
\end{equation}
\begin{equation}
P_{{\cal S},k}(n)=  \sum_{d\mid n} \phi(d) \binom{n/d}{k} \quad
(n\ge 1),
\end{equation}
\begin{equation}
\sum_{n\le x} P_{{\cal S},k}(n)= \frac{\zeta(k)}{(k+1)!\zeta(k+1)}
x^{k+1} + {\cal O}(\psi_k(x)) \quad (k\ge 2),
\end{equation}
where $\psi_k(x)=x^k$ for $k\ge 3$ and $\psi_2(x)=x^2\log x$.


%************************* Section 6 *******************************************


\section{Open problems} \label{section 6}

Here I list some open problems concerning the functions discussed
above.

{\bf 1.} Determine the integers $n\ge 1$ such that $n\mid P(n)$,
that is $\sum_{d\mid n} \frac{\phi(d)}{d}$ is an integer.

The first few values are: $1, 4, 15, 16, 27, 48, 60, 64, 108, 144,
240, 256, 325, 432, 729, 891, 960$. This is sequence
\seqnum{A066862} in Sloane's Encyclopedia. From \eqref{prime_pow} it
is clear that $n=\prod_{i=1}^r p_i^{a_ip_i}$ are solutions for any
distinct primes $p_i$ and any $a_i\ge 1$.

For square-free values $n=\prod_{i=1}^r p_i$ this is equivalent to
$\prod_{i=1}^r \left(2-\frac1{p_i}\right)$ be an integer. It can be
shown that the only square-free solutions having at most three
distinct prime factors are $n=1$ and $n=15$.

I conjecture that there are no other square-free solutions. I have
verified this for the integers $n<10^6$.

{\bf 2.} Determine the integers $n\ge 1$ such that $n\mid
\widetilde{P}(n)$. This holds iff $\prod_{p\mid
n}\left(2-\frac1{p}\right)$ is an integer. If the previous
conjecture is true, then the only integers solutions to the present
problem are $n=1$ and $n=15$.

{\bf 3.} Investigate the equation
$\widetilde{P}(n)=\widetilde{P}(n+1)$.

The first few solutions are: $45, 225, 1125, 2025, 3645, 140 625,
164 025, 257 174$. According to de Koninck and K\'atai
\cite{KonKat2010} this equation has $37$ solutions $<10^{10}$ and
$21$ of them are of form $n=3^a5^b$.

{\bf 4.} What is the minimal order of $P(n)$ ($P^*(n)$)?

{\bf 5.} Derive asymptotic formulae for $\sum_{n\le x} (f(n))^k$,
where $f$ is one of the functions $P$, $P^*$, $P^{(e)}$,
$\widetilde{P}$ and $k>2$.

{\bf 6.} Investigate asymptotic properties of the iterates
$f(f(n))$, where $f$ is one of the functions $P$, $P^*$, $P^{(e)}$,
$\widetilde{P}$.



%************************* Section 7 *******************************************

\section{Added in proof} \label{section 7}

The author thanks the anonymous referee for helpful suggestions and
for the following results concerning $\sum_{n\le x} 1/f(n)$, where
$f$ is any of the functions $P$, $P^*$, $P^{(e)}$, $\widetilde{P}$.
The problem of finding such asymptotic formulae was included
originally in the previous section.

\begin{thm}
\begin{equation} \label{1/P}
\sum_{n\le x} \frac1{P(n)}= K(\log x)^{1/2} +{\cal O}((\log
x)^{-1/2}),
\end{equation}
\begin{equation} \label{1/P*}
\sum_{n\le x} \frac1{P^{*}(n)}= K^*(\log x)^{1/2} +{\cal O}((\log
x)^{-1/2}),
\end{equation}
\begin{equation} \label{1/P_reg}
\sum_{n\le x} \frac1{\widetilde{P}(n)}= \widetilde{K} (\log x)^{1/2}
+{\cal O}((\log x)^{-1/2}),
\end{equation}
\begin{equation} \label{1/P_exp}
\sum_{n\le x} \frac1{P^{(e)}(n)}= K^{(e)} \log x +{\cal O}(1),
\end{equation}
where
\begin{equation}
K = \frac{2}{\sqrt{\pi}}\prod_p \left(1-\frac1{p}\right)^{1/2}
\left( 1+\sum_{a=1}^{\infty} \frac1{P(p^a)} \right),
\end{equation}
\begin{equation}
K^*= \frac{2}{\sqrt{\pi}}\prod_p \left(1-\frac1{p}\right)^{1/2}
\left( 1+\sum_{a=1}^{\infty} \frac1{2p^a-1} \right),
\end{equation}\begin{equation}
\widetilde{K} = \frac{2}{\sqrt{\pi}}\prod_p
\left(1-\frac1{p}\right)^{1/2} \left( 1+ \frac1{p-1}-\frac1{2p-1}
\right) \approx 1.46851,
\end{equation}\begin{equation}
K^{(e)} = \prod_p \left(1-\frac1{p}\right) \left(
1+\sum_{a=1}^{\infty} \frac1{P^{(e)}(p^a)} \right).
\end{equation}
\end{thm}

For the proof we apply the following useful theorem, which is a
particular case of a more general result, proved by Martin
\cite{Mar2002}.

{\it Theorem {\rm \cite[Proposition A. 3]{Mar2002}}. Let f be any
nonnegative multiplicative function such that $f(n)\ll n^{\alpha}$
for some $\alpha < 1/2$ and satisfying
\begin{equation*}
\sum_{p\le x} \frac{f(p)\log p}{p} = \kappa \log x + {\cal O}_f(1)
\quad (x\ge 2),
\end{equation*}
where $\kappa=\kappa_f>0$. Then we have uniformly for all $x \ge 2$,
\begin{equation} \label{propA.3}
\sum_{n\le x} \frac{f(n)}{n} ={\cal M}_{f,\kappa}(\log x)^{\kappa}
+{\cal O}_f((\log x)^{\kappa-1}),
\end{equation}
where
\begin{equation*}
{\cal M}_{f,\kappa}= \frac1{\Gamma(\kappa+1)}\prod_p \left(1
-\frac1{p}\right)^{\kappa} \left(1+\sum_{a=1}^{\infty}
\frac{f(p^a)}{p^a} \right).
\end{equation*}}

Let $f(n)=n/P(n)$, which is multiplicative and by \eqref{prime_pow},
$\displaystyle f(p^a)=\frac{p}{(a+1)p-a}$ for any prime power $p^a$
($a\ge 1$). Hence $\displaystyle f(p^a)\le \frac{2}{a+1}$ and
$\displaystyle f(n)\le \frac{2^{\omega(n)}}{\tau(n)}\le 1$ for any
$n\ge 1$. Since
\begin{equation*}
\sum_{p\le x} \frac{f(p)\log p}{p}=\sum_{p\le x} \frac{\log
p}{p}\left(\frac1{2} + \frac1{4p-2} \right)= \frac1{2}\log x+{\cal
O}(1),
\end{equation*}
the cited theorem gives the formula \eqref{1/P}, by choosing
$\kappa=1/2$, where $\Gamma(3/2)=\sqrt{\pi}/2$.

By similar arguments we obtain formulae \eqref{1/P*},
\eqref{1/P_reg} and \eqref{1/P_exp}.

%************************* References *******************************************
\begin{thebibliography}{99}

\bibitem{All1975} K.~Alladi, On generalized Euler functions
and related totients, in {\it New Concepts in Arithmetic Functions},
Matscience Report 83, Madras, 1975.

\bibitem{And1971} G.~E.~Andrews, {\it Number Theory}, W. B. Saunders, 1971.

\bibitem{BalRot2008} M.~Balazard and A.~De~Roton, Notes de lecture de l'article ``Partial
sums of the M\"obius function'' de Kannan Soundararajan (French),
Preprint, 2008.  Available at \url{http://front.math.ucdavis.edu/0810.3587}.

\bibitem{Beg2006} A.~Bege, {\it Old and New Arithmetic Functions}
(Hungarian), Scientia, Kolozsv\'ar [Cluj-Napoca], 2006.

\bibitem{Bor2007a} O.~Bordell\`{e}s, A note on the average order of the gcd-sum
function, {\it J. Integer Sequences} {\bf 10} (2007),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles/bordelles90.html}
{Article 07.3.3}.

\bibitem{Bor2007b} O.~Bordell\`{e}s, Mean values of generalized gcd-sum and
lcm-sum functions, {\it J. Integer Sequences} {\bf 10} (2007),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles2/bordelles61.html}
{Article 07.9.2}.

\bibitem{Bor2010} O.~Bordell\`{e}s, The composition of the gcd and certain arithmetic functions,
{\it J. Integer Sequences} {\bf 13} (2010),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Bordelles/bordelles6.html}{Article
10.7.1}.

\bibitem{Bro2001} K.~A.~Broughan, The gcd-sum
function, {\it J. Integer Sequences} {\bf 4} (2001),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/BROUGHAN/gcdsum.html}
{Article 01.2.2}.

\bibitem{Bro2007} K.~A.~Broughan, The average order of the Dirichlet series of
the gcd-sum function, {\it J. Integer Sequences} {\bf 10} (2007),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Broughan/broughan1.html}
{Article 07.4.2}.

\bibitem{ChiSit1985} J.~Chidambaraswamy and R.~Sitaramachandrarao, Asymptotic
results for a class of arithmetical functions, {\it Monatsh. Math.}
{\bf 99} (1985), 19--27.

\bibitem{Coh1960i} E.~Cohen, Arithmetical functions of a greatest common divisor,
I., {\it Proc. Amer. Math. Soc.} {\bf 11} (1960), 164--171.

\bibitem{Coh1962ii} E.~Cohen, Arithmetical functions of a greatest common divisor,
II. An alternative approach, {\it Boll. Un. Mat. Ital.} {\bf 17}
(1962), 349--356.

\bibitem{Coh1961iii} E.~Cohen, Arithmetical functions of a greatest common divisor,
III. Ces\`{a}ro's divisor problem, {\it Proc. Glasgow Math. Assoc.}
{\bf 5} (1961-1962), 67--75.

\bibitem{DiaErd2004} P.~Diaconis and P.~Erd\H os, On the distribution of the
greatest common divisor, in {\it A festschrift for Herman Rubin, IMS
Lecture Notes Monogr. Ser., Inst. Math. Statist.}, {\bf 45}, (2004),
56-61 (original version: Technical Report No. 12, Department of
Statistics, Stanford University, Stanford, 1977).  

\bibitem{Dic1952} L.~E.~Dickson, {\it History of the Theory of Numbers}, vol. 1,
Chelsea, New York, 1952.

\bibitem{Fin2003} S.~R.~Finch, {\it Mathematical Constants}, Cambridge
University Press, 2003.

\bibitem{zGat2004} J.~von zur Gathen, A.~Knopfmacher, F.~Luca, L.~G.~Lucht,
and I.~E.~Shparlinski,
Average order in cyclic groups, {\it J. Th\'eor. Nombres Bordeaux}
{\bf 16} (2004), 107--123.
Available at
\url{http://www.numdam.org/item?id=JTNB_2004__16_1_107_0}.

\bibitem{GouSho1997} H.~W.~Gould and T.~Shonhiwa, Functions of GCD's and LCM's,
{\it Indian J. Math.} {\bf 39} (1997), 11--35.

\bibitem{Hau1999} P.~Haukkanen, Rational arithmetical functions of order $(2,1)$
with respect to regular convolutions, {\it Portugal. Math.} {\bf 56}
(1999), 329--343.

\bibitem{Hau2008} P.~Haukkanen, On a gcd-sum function,
{\it Aequationes Math.} {\bf 76} (2008), 168--178.

\bibitem{Hux2003} M.~N.~Huxley, Exponential sums and
lattice points III., {\it Proc. London Math. Soc.} {\bf 87} (2003),
591--609.

\bibitem{Ivi2006} A.~Ivi\`{c}, E.~Kr\"atzel, M.~K\"uhleitner,
and W.~G.~Nowak, Lattice points in large regions and
related arithmetic functions: recent developments in a very classic
topic, Elementare und analytische Zahlentheorie, {\it Schr. Wiss.
Ges. Johann Wolfgang Goethe Univ. Frankfurt am Main}, {\bf 20},
89--128, Franz Steiner Verlag Stuttgart, 2006.

\bibitem{Kes1965} P.~Kesava~Menon, On the sum $\sum (a-1,n) [(a, n) = 1]$, {\it J. Indian
Math. Soc.} {\bf 29} (1965), 155--163.

\bibitem{KonKat2010} J.-M.~de~Koninck and
I.~K\'atai, Some remarks on a paper of L. Toth,
{\it J. Integer Sequences} {\bf 13} (2010),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/DeKoninck/dekoninck7.html}{Article
10.1.2}.

\bibitem{Kop1977} H.~G.~Kopetzky, Ein asymptotischer Ausdruck f\"ur eine
zahlentheoretische Funktion, {\it Monatsh. Math.} {\bf 84} (1977),
213--217.

\bibitem{Lau1989} Kee-Wai~Lau, Problem 6615, {\it Amer. Math. Monthly} {\bf 96} (1989),
847, solution in {\bf 98} (1991), 562--565.

\bibitem{Lov2006} A.~D.~Loveless, General gcd-product function, {\it
Integers} {\bf 6} (2006), Paper A19, 13 pp, corrigendum Paper A39.

\bibitem{Mar2002} G.~Martin, An asymptotic formula for the number of smooth values
of a polynomial, {\it J. Number Theory} {\bf 93} (2002), 108--182.

\bibitem{McC1986} P.~J.~McCarthy, {\it Introduction to Arithmetical Functions},
Uni\-ver\-si\-text, Springer, 1986.

\bibitem{Min2009} N.~Minami, On the random variable $\N \ni l \mapsto \gcd(l,n_1) \gcd(l,
n_2)\cdots \gcd(l,n_k)\in \N$, Preprint, 2009. Available at
\url{http://arxiv.org/abs/0907.0918}.

\bibitem{MonVau2007} H.~L.~Montgomery and R.~C.~Vaughan,
{\it Multiplicative Number Theory I. Classical Theory}, Cambridge
University Press, 2007.

\bibitem{NivZuc1972} I.~Niven and H.~S.~Zuckerman, {\it An Introduction to the
Theory of Numbers}, 3th edition, John Wiley \& Sons, 1972.

\bibitem{Pet1998} Y.-F.~S.~P\'etermann, On an estimate of Walfisz and
Saltykov for an error term related to the Euler function, {\it J.
Th\'eor. Nombres Bordeaux} {\bf 10} (1998), 203--236.

\bibitem{Pet} Y.-F.~S.~P\'etermann, Arithmetical functions involving
exponential divisors: Note on two papers by L. T\'oth, {\it Annales
Univ. Sci. Budapest., Sect. Comp.}, to appear.

\bibitem{Pil1933} S.~S.~Pillai, On an arithmetic function, {\it J. Annamalai
Univ.} {\bf 2} (1933), 243--248.

\bibitem{SanCrs2004} J.~S\'andor and B.~Crstici, {\it Handbook of Number Theory II.},
Kluwer Academic Publishers, 2004.

\bibitem{SanKra1999} J.~S\'andor and A.-V.~Kramer, \"Uber eine
zahlentheoretische Funktion, {\it Math. Morav.} {\bf 3} (1999),
53--62.

\bibitem{Sch2008} W.~Schramm, The Fourier transform of functions of the greatest
common divisor, {\it Integers} {\bf 8} (2008), \#A50.

\bibitem{Sha1980} J.~Shallit, Problem E 2821, {\it Amer. Math.
Monthly} {\bf 87} (1980), 220. Solution in {\bf 88} (1981),
444--445.

\bibitem{Siv1971} R.~Sivaramakrishnan, On three extensions of Pillai's
arithmetic function $\beta(n)$, {\it Math. Student} {\bf 39} (1971),
187--190.

\bibitem{ShoGou1997} T.~Shonhiwa and H.~W.~Gould, A generalization of
Ces\`{a}ro's function and other results, {\it Indian J. Math.} {\bf
39} (1997), 183--194.

\bibitem{Sou2009} K.~Soundararajan, Partial sums of the M\"obius function, {\it J.
Reine Angew. Math.} {\bf 631} (2009), 141--152.

\bibitem{SurSit1973} D.~Suryanarayana and R.~Sitaramachandra Rao, On
an asymptotic formula of Ramanujan, {\it Math. Scand.} {\bf 32}
(1973), 258--264.

\bibitem{Teu1970} E.~Teuffel, Aufgabe 599, {\it Elem. Math.} {\bf 25} (1970),
65--66.

\bibitem{TanZha2008} Y.~Tanigawa and W.~Zhai, On the gcd-sum function, {\it J.
Integer Sequences} {\bf 11} (2008),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Tanigawa/tanigawa12.html}{Article
08.2.3}.

\bibitem{Tit1986} E.~C.~Titchmarsh, {\it The Theory of the Riemann
Zeta Function}, Second edition, Edited and with a preface by D. R.
Heath-Brown, Clarendon Press, Oxford University Press, New York,
1986.

\bibitem{Tot1989} L.~T\'oth, The unitary analogue of Pillai's
arithmetical function, {\it Collect. Math.} {\bf 40} (1989), 19--30.

\bibitem{Tot1990} L.~T\'oth,
Some remarks on a generalization of Euler's function,
{\it Semin. Arghiriade} {\bf 23} (1990).

\bibitem{Tot1996} L.~T\'oth, The unitary analogue of Pillai's arithmetical
function II., {\it Notes Number Theory Discrete Math.} {\bf 2}
(1996), no.\ 2, 40--46.  Available at
\url{http://www.ttk.pte.hu/matek/ltoth/Toth_Pillai2_1996.pdf}.

\bibitem{Tot1998} L.~T\'oth, A generalization of Pillai's arithmetical function
involving regular convolutions, Proceedings of the 13th Czech and
Slovak International Conference on Number Theory (Ostravice, 1997),
{\it Acta Math. Inform. Univ. Ostraviensis} {\bf 6} (1998),
203--217.  Available at \url{http://dml.cz/dmlcz/120534}.

\bibitem{Tot2004} L.~T\'oth, On certain arithmetic functions involving
exponential divisors, {\it Annales Univ. Sci. Budapest., Sect.
Comp.} {\bf 24} (2004), 285--294.  Available at
\url{http://front.math.ucdavis.edu/0610.5274}.

\bibitem{Tot2008} L.~T\'oth, Regular integers (mod $n$), {\it Annales Univ. Sci.
Budapest., Sect. Comp.} {\bf 29} (2008), 263--275.  Available at
\url{http://front.math.ucdavis.edu/0710.1936}.

\bibitem{Tot2009reg} L.~T\'oth, A gcd-sum function over regular integers (mod
$n$), {\sl J. Integer Sequences} {\bf 12} (2009),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Toth/toth3.html}
{Article 09.2.5}.

\bibitem{Tot2009bi} L.~T\'oth, On the bi-unitary analogues of Euler's
arithmetical function and the gcd-sum function, {\sl J. Integer
Sequences} {\bf 12} (2009),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Toth2/toth5.html}{Article
09.5.2}.

\bibitem{Tot2010} L.~T\'oth, On the number of certain relatively prime subsets of $\{1,2,\ldots,
n\}$, {\it Integers}, to appear.

\bibitem{Vas1966} A.~C.~Vasu, On a certain arithmetic function, {\it Math.
Student} {\bf 34} (1966), 93--95.

\bibitem{Wil1922} B.~M.~Wilson, Proofs of some formulae enunciated by Ramanujan,
{\it Proc. London Math. Soc.} (2) {\bf 21} (1922), 235--255.

\bibitem{ZhaZha2010} D.~Zhang and
W.~Zhai, Mean values of a gcd-sum function over regular integers modulo $n$,
{\sl J. Integer Sequences} {\bf 13} (2010),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Zhang/zhang10.html}{Article
10.4.7}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11A25; Secondary 11N37.

\noindent \emph{Keywords:} gcd-sum function, Euler's arithmetical
function, divisor function, unitary divisor, exponential divisor,
regular integer (mod $n$), average order.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A001880},
\seqnum{A018804},
\seqnum{A047994},
\seqnum{A057660},
\seqnum{A066862},
\seqnum{A067911},
\seqnum{A145388}, and
\seqnum{A176345}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 29 2010;
revised version received  July 20 2010.
Published in {\it Journal of Integer Sequences}, August 2 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.
