% 21.04.06 12.01.07 24.06.07 (revision for submission)
\documentclass[12pt]{article}
\usepackage{latexsym}
%\usepackage{amsfonts}
\textwidth= 6.25in 
\textheight= 9.0in 
\topmargin = -10pt
\evensidemargin=10pt 
\oddsidemargin=10pt 
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10 
\font\smalltt=cmtt10 
\font\smallrm=cmr9
%\usepackage{amsfonts}
\usepackage{amssymb}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newcommand{\proof}{\noindent {\it Proof.}\ }
%\newcommand{\N}{\mbox{\rm I}\!\mbox{\rm N}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\QED}{\hfill $\Box$}
\newcommand{\qed}{\hfill $\Box$}

\makeatletter

\renewcommand\section{\@startsection {section}{1}{\z@}%
% {-3.5ex \@plus -1ex \@minus -.2ex}%
% here is the vskip of 30pt:
{-30pt \@plus -1ex \@minus -.2ex}%
{2.3ex \@plus.2ex}%
{\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
{-3.25ex\@plus -1ex \@minus -.2ex}%
{1.5ex \@plus .2ex}%
{\normalfont\normalsize\bfseries}}
% add a point after section numbers: 
\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad} 

\makeatother

\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A33}
\vskip 40pt

\begin{center}
\uppercase{\bf On factorization of integers with restrictions on the
exponents}
\vskip 20pt 
{\bf Simon Litsyn\footnote{Partly supported by ISF Grant 033-06}}\\
{\smallit School of
Electrical Engineering, Tel Aviv University, Ramat Aviv 69978 Israel}\\
{\tt litsyn@eng.tau.ac.il}\\
\vskip 10pt
{\bf Vladimir Shevelev\footnote{Partly supported by the Kamea program of the
Israeli Ministry of Absorption}}\\
{\smallit Department of Mathematics, Ben Gurion
University of the Negev, Beer Sheva 84105 Israel}\\
{\tt shevelev@bgu.ac.il}\\
\end{center}
\vskip 30pt\centerline{\smallit Received: 1/19/07,
Accepted: 6/24/07, Published: 7/20/07} 
\vskip 30pt



\centerline{\bf Abstract}
\noindent
For a fixed $k \in \N$ we consider a multiplicative basis in $\N$
such that every $n \in \N$ has the unique factorization as product
of elements from the basis with the exponents not exceeding $k$. We
introduce the notion of $k$-multiplicativity of arithmetic
functions, and study several arithmetic functions naturally defined
in $k$-arithmetics. We study a generalized Euler function and prove
analogs of the Wirsing and Delange theorems for $k$-arithmetics.

\vskip 20pt
\footnotesize
\noindent MSC: Primary 11A51, 11A25; Secondary 11N37

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL
 OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A33\hfill} 

\thispagestyle{empty} \baselineskip=15pt

\normalsize

\section{Introduction}

Let
\begin{equation} \label{eq:1} n=\prod_{p \in \mathbf{P}} p^{n_p}
\end{equation}
be the canonical factorization of an integer $n$ to prime powers. In
other words, the set $\{p \in {\bf P}\}$ constitutes a multiplicative
basis in $\N$ and $n_p$ can take any non-negative integer values. In
the paper we consider other multiplicative bases such that any
integer has a unique factorization with the exponents not
exceeding some prescribed value $k$. For example, if $k=1$, then the
only such basis is
$$Q^{(1)}=\{p^{2^j}, p \in \mathbf{P}, j=0,1,\dots ,\infty\},$$
and every integer $n$ has the unique factorization
$$ n=\prod_{q \in Q^{(1)}} q^{n_q}, \quad n_q \in \{0,1\}.$$

For arbitrary $k$, the basis is
$$Q^{(k)}=\{p^{(k+1)^j}, p \in \mathbf{P}, j=0,1,\dots ,\infty\},$$
and the corresponding $k$-factorization is
\begin{equation} \label{eq:2}
n=\prod_{q \in Q^{(k)}} q^{n_q}, \quad n_q \in \{0,1,\dots ,k\}.
\end{equation}

\begin{example}{\rm For $k=2$ we have the ordered basis
$$Q^{(2)}=\{2,3,5,7,8,11,13,17,19,23,27,29,\dots ,512,\dots \},$$
and, for example, $35831808=2^2 \cdot 3^1 \cdot 8^1 \cdot 27^2
\cdot 512^1.$}
\end{example}

Notice that the standard prime basis ${\bf P}$ is the limiting for
$k$ tending to $\infty$, and, by definition, ${\bf P}=Q^{(\infty)}.$

For a fixed $k$ we use the term $k$-primes for the elements of
$Q^{(k)}$. We say that a number $d$ is $k$-divisor of $n$ if the
exponents in the $k$-factorization of $d$, $d_q$, do not exceed
$n_q$.

In this paper we study some non-trivial generalizations of classical
arithmetic functions for the introduced $k$-factorization. It is
organized as follows. We start with some basic relations in Section
\ref{sec:basic}. In Section \ref{sec:unitary} we define $k$-unitary
and $k$-polynitary divisors and demonstrate that in contrast to the
standard $\infty$-arithmetics in $k$-arithmetics the maximal
divisors are $(k-1)$-ary divisors. In Section \ref{sec:function} we
study the $k$-integer part of ratios and provide an explicit and
asymptotic expressions for it. A $k$-equivalent of the Euler totient
function is introduced in Section \ref{sec:totient}, and an explicit
and asymptotic formula for it is given. The classical asymptotic
Mertens formula is generalized in Section \ref{sec:sums}.  In
Section \ref{sec:other} we study the average of the sums of
$k$-divisors and some other generalized number-theoretic functions.
In Section \ref{sec:relations} we prove some results about relations
between the classical Euler totient function and its
$k$-generalization. In Section \ref{sec:wirsing} we develop
$k$-analogs of the classical Delange and Wirsing theorems for
$k$-multiplicative functions. Generalizations of the perfect numbers
are considered in Section \ref{sec:perfect}.  In Section
\ref{sec:mix} we study bases associated with $k$-prime numbers for
different $k$'s. Open problems are summarized in Section
\ref{sec:open}.

Particular cases of the described problems were considered
earlier. The case of $k=1$ was introduced in 1981 in
\cite{shev81}. Later in \cite{shev96} a class of multiplicative
functions for $k=1$ was addressed. In 1990 G.~L.~Cohen
\cite{cohe90} introduced the so-called infinitary arithmetics
coinciding with the considered situation when $k=1$. In the same
paper Cohen treated {\it infinitary perfect numbers} coinciding
with {\it harmonic numbers} from \cite{shev82}. These numbers were
also considered in \cite{pede04,shev96,weis}. Cohen and Hagis
\cite{cohe93} analyzed some arithmetic functions associated with
infinitary divisors. A survey of unitary and infinitary analogs of
arithmetic functions is by Finch \cite{finc04}, see also Weisstein
\cite{weis}. Notice that D.~Suryanarayana \cite{sury68} introduced
a definition of $k$-ary divisors different from the one considered
in this paper.

\section{Basic Relations} \label{sec:basic}

Let $k \in \N$. Consider  the factorization of $n_p$, see (\ref{eq:1}),
in the basis of $(k+1)$,
\begin{equation} \label{eq:2*}
n_p=\sum_{i \ge 0} a_i (k+1)^i,
\end{equation}
where $a_i=a_i(n_p)$ are integers belonging to $[0,k]$. Substituting
(\ref{eq:2*}) into (\ref{eq:1}) we find
\begin{equation} \label{eq:3} n=\prod_{p \in {\bf P}} \prod_{i \ge 0}
p^{a_i (k+1)^i }=\prod_{p \in {\bf P}} \prod_{i \ge 0} \left(
p^{(k+1)^i}\right)^{a_i}.
\end{equation}
The uniqueness of (\ref{eq:1}) and (\ref{eq:2*}) yields the
uniqueness of factorization (\ref{eq:3}). Therefore, the unique
multiplicative basis in $k$-arithmetic consists of $k$-primes
\begin{equation} \label{eq:4}
Q^{(k)}=\left\{ p^{(k+1)^{j-1}}\,:\, p \in {\bf P}, j \in \N
\right\},
\end{equation}
and by (\ref{eq:3}) the canonical factorization of an integer $n$ is
\begin{equation} \label{eq:5}
n=\prod_{q \in Q^{(k)}} q^{n_q^{(k)}},
\end{equation}
with $n_q^{(k)} \le k$.

To every $n$ we associate the finite multi-set $Q_n^{(k)}$ of
$k$-primes of multiplicity defined by (\ref{eq:5}). For every $k \ge
1$ we assume $Q_1^{(k)}=\emptyset$.

\begin{definition} \label{defi:1} A number $d$ is called a
{\rm $k$-divisor of $n$} if $Q_d^{(k)} \subseteq Q_n^{(k)}$. 
\end{definition}

We write $d {| \atop k} n$ if $d$ is a $k$-divisor of $n$. Set
\begin{equation} \label{eq:6}
(n_1,n_2)_k=\max_{d{| \atop k}n_1, d{| \atop k}n_2} \ d.
\end{equation}
It is easy to see that $Q^{(k)}_{(n_1,n_2)_k}=Q^{(k)}_{n_1} \cap
Q^{(k)}_{n_2}$.

\begin{definition} \label{eq:defi2} Numbers $n_1$ and $n_2$ are
called {\rm mutually $k$-prime} if $(n_1,n_2)_k=1$. 
\end{definition}

Notice that the mutual $k$-primality for $k \ge 1$ is weaker than
the mutual primality in the ordinary arithmetics. Indeed,
$(n_1,n_2)=1$ yields $(n_1,n_2)_k=1$ for any $k>1$. However, the
last equality could be valid also when $(n_1,n_2)>1$. For example,
$\left(2^{(k+1)^2}, 3 \cdot 2^{k+2} \right)_k=1$ for every $k$.

\begin{definition} A function $\theta(n)$ is called {\rm
$k$-multiplicative} if it is defined for all natural $n$ in such a way
that $\theta(n)
\neq 0$, and for mutually $k$-prime $n_1$ and $n_2$ we have
\begin{equation} \label{eq:7}
\theta(n_1 n_2)=\theta(n_1) \theta(n_2).
\end{equation}
\end{definition}

From the definition it follows that $\theta(1)=1$. In the
conventional arithmetics the $k$-multiplicative functions can be
positioned in between the multiplicative functions and
strongly-multiplicative functions (for which (\ref{eq:7}) holds for
any $n_1$ and $n_2$). Let us list several examples of $k$-analogs
following from (\ref{eq:5}) for generalizations of well-known
properties of multiplicative functions, see e.g.
\cite{chan68,post88}.

Let $\theta(n)$ be a $k$-multiplicative function. Then, using $q$ to
denote $k$-primes, we have
\begin{equation} \label{eq:8}
\sum_{d {| \atop k} n} \theta(d)=\prod_{q {| \atop k} n}
\left(1+\sum_{i=1}^{n_q^{(k)}} \theta(q^i)\right) \quad \mbox{ and }
\end{equation}
\begin{equation} \label{eq:9}
\sum_{d {| \atop k} n} \mu_k(d) \theta(d)=\prod_{q {|\atop k}n}
(1-\theta(q)),
\end{equation}
where
\begin{equation} \label{eq:10}
\mu_k(n)=\left\{\begin{array}{ll} 0, & \mbox{\rm if there exists\  }  q
\in Q^{(k)}: q^2 {| \atop k} n, \\
(-1)^{\sum_{q {\tiny {| \atop k}} n} 1}, & \mbox{\rm otherwise.}
\end{array} \right.
\end{equation}
The function $\mu_k(n)$ is the analog of the M\"{o}bius function in
$k$-arithmetics.  A distinction of $\mu_k(n)$ from $\mu(n)$ is, for
example, in that when $\mu_k(n) \neq 0$ then $n$ is not necessary
square-free in the conventional sense.

When $\theta(q)=1$ it follows from (\ref{eq:9}) that
\begin{equation} \label{eq:11}
\sum_{d {| \atop k} n} \mu_k(d)= \left\{\begin{array}{ll} 0, &
\mbox{\rm
if\ } n>1,\\
1, & \mbox{\rm if\ } n=1.
\end{array} \right.
\end{equation}
Furthermore, (see, e.g., \cite{chan68} for the absolutely converging
series $\sum_{n=1}^\infty \theta(n)$) we have
\begin{equation} \label{eq:12}
\sum_{n=1}^\infty \theta(n)=\prod_{q \in Q^{(k)}}
(1+\theta(q)+\cdots +\theta(q^k)).
\end{equation}
Considering here $\mu_k(n) \theta(n)$ instead of $\theta(n)$, by
(\ref{eq:10}), we find
\begin{equation} \label{eq:13}
\sum_{n=1}^\infty \mu_k(n) \theta(n)=\prod_{q \in Q^{(k)}}
(1-\theta(q)).
\end{equation}
On the other hand, for $\theta(n)=n^{-s}$, $\Re(s)>1$, an analog of
the Euler identity in $k$-arithmetics follows:
\begin{equation} \label{eq:14}
\zeta(s)=\prod_{q \in Q^{(k)}} \frac{1-q^{-(k+1)s}}{1-q^{-s}}.
\end{equation}


\section{Unitary and Polynitary Divisors} \label{sec:unitary}

Recall that a unitary divisor of a number $n$ in classical
arithmetics is a divisor $d$ of $n$ for which $\left(\frac{n}{d},d
\right)=1$. Let $(n,m)^{(1)}$ stand for the greatest unitary divisor
of $n$ and $m$. Then a divisor $d$ is called bunitary if $\left(
\frac{n}{d},d \right)^{(1)}=1$. Analogously we may inductively
define $\ell$-ary divisors of $n$ satisfying $\left( \frac{n}{d},d
\right)^{(\ell-1)}=1$. We write in this case $d|^{(\ell)}n$. The
infinitary divisors are limiting in this process ($\ell=\infty$). As
it was mentioned, they were introduced by G.~L.~Cohen \cite{cohe90}.

\begin{definition} \label{defi:4}
If $d {| \atop k} n$, then $d$ is called {\rm $k$-unitary}, or a
{\rm $(1)_k$-ary divisor of $n$}, if $\left(\frac{n}{d},d \right)_k=1$.
\end{definition}

Let us denote by $(n,m)_k^{(1)}$ the greatest common $k$-unitary
divisor of $n$ and $m$.

\begin{definition} \label{defi:5}
If $d {| \atop k} n$ then $d$ is called {\rm $k$-bunitary}, or a
{\rm $(2)_k$-ary divisor}, if $\left(\frac{n}{d},d \right)_k^{(1)}=1$.
Furthermore, if $(n,m)_k^{(\ell-1)}$ is the greatest common
$(\ell-1)_k$-ary divisor of $n$ and $m$, then a divisor $d$ of $n$
is called $(\ell)_k$-ary if $\left(
\frac{n}{d},d\right)_k^{(\ell-1)}=1$. \qed
\end{definition}

By convention, $d$ is called a $(0)_k$-ary divisor if $d {| \atop k}
n$. We will write $d {| \atop k}^{(\ell)}$ when we wish to indicate
that $d$ is an $(\ell)_k$-ary divisor of $n$.

Let us show that, in contrast to the classical arithmetics, in
$k$-arithmetics, $k < \infty$, there exist divisors of maximal index
$\ell$. Such are $(k-1)_k$-ary divisors. The following iterations of
the considered process do not change the $(k-1)_k$-arity of the
divisors. In other words, whenever $\ell \ge k-1$, the
$(\ell)_k$-ary divisors are $(k-1)_k$-ary divisors.

For the proof we employ the following statement due to Cohen
\cite{cohe90}:

\noindent {\it If $p$ is a prime, then for an integer $y \in
[0,\ell]$, and an integer $x \in [0,y]$, we have}
\begin{equation} \label{eq:15}
p^x |^{(\ell-1)} p^y \Leftrightarrow p^x |^{(y-1)} p^y.
\end{equation}

To prove it one should use a trivial fact that the only factors of
$p^y$ are $1, p,\dots ,p^y$. For $y \le k$ this is true for any
$k$-prime $q \in Q^{(k)}$. Therefore, analogously to (\ref{eq:15})
for $y \in [0,k]$, we have
\begin{equation} \label{eq:16}
p^x {| \atop k}^{(k-1)} p^y \Leftrightarrow p^x {| \atop k}^{(y-1)}
p^y.
\end{equation}

Analogously, by (\ref{eq:15}), for $y \in [0,k+1]$, we obtain
\begin{equation} \label{eq:17}
p^x |^{(k)} p^y \Leftrightarrow p^x |^{(y-1)} p^y.
\end{equation}

However, the last identity is valid in both, the conventional and
$k$-arithmetics. Indeed, for $y \le k$ by (\ref{eq:16}) and
(\ref{eq:17}),
$$p^x {| \atop k}^{(k-1)} p^y \Leftrightarrow p^x {| \atop k}^{(k)}
p^y,$$ and for $y=k+1$, (\ref{eq:17}) becomes a tautology.
Therefore, in $k$-arithmetics we have for all $y$,
$$p^x {| \atop k}^{(k)} p^y \Leftrightarrow p^x {| \atop k}^{(k-1)}
p^y,$$ and the claim easily follows.

In particular,
$$p^x {| \atop 1}^{(1)} p^y \Leftrightarrow p^x {| \atop 1}^{(0)}
p^y,$$ or $p^x {| \atop 1} p^y$, i.e. in $1$-arithmetics all the
divisors are $1$-unitary.


\section{The Function $\left\lfloor \frac{x}{m} \right\rfloor^{(k)}$}
\label{sec:function}

Let us introduce the function $\lfloor \frac{x}{m} \rfloor^{(k)}$
being a natural generalization of the function $\lfloor \frac{x}{m}
\rfloor$ as a function in $x$ for a fixed $m$. We use $\lfloor
\frac{x}{m} \rfloor^{(k)}$ to denote the number of integers not
exceeding $x$ for which $m$ is a $k$-divisor. In contrast to
$\lfloor \frac{x}{m} \rfloor,$ as will be seen from what follows,
there is in principle no algorithm for computing $\lfloor
\frac{x}{m} \rfloor^{(k)}$, if the canonical factorization of $m$ in
$k$-arithmetics is not known. Moreover, without such factorization
it is impossible even to compute the main asymptotical term of
$\lfloor \frac{x}{m} \rfloor^{(k)}$ for $x \rightarrow \infty$. The
following theorem gives an explicit expression for $\lfloor
\frac{x}{m} \rfloor^{(k)}$.

\subsection{An Exact Formula for $\left\lfloor
\frac{x}{m} \right\rfloor^{(k)}$}

\begin{theorem} \label{thm:1}
Let $m =q_1^{\ell_1} q_2^{\ell_2}\dots  q_r^{\ell_r}$, $1 \le \ell_i \le
k$, be the $k$-factorization of $m$ (notice, that the indices of
$q_i$'s are not necessary their consecutive numbers in the ordered
sequence of $Q^{(k)}$). Then for positive real $x \ge m$,
\begin{equation} \label{eq:18}
\left\lfloor \frac{x}{m} \right\rfloor^{(k)}=\sum_{j_1 \ge \ell_1}
\sum_{j_2 \ge \ell_2} \dots  \sum_{j_r \ge \ell_r} \left( \left(
\prod_{i=1}^r a_{j_i}^{(\ell_i)} \right) \left\lfloor
\frac{x}{\prod_{i=1}^r q_i^{j_i}} \right\rfloor \right),
\end{equation}
where for fixed $\ell>0$,
\begin{equation} \label{eq:19}
a_j^{(\ell)}=\left\{\begin{array}{rl} 1 & \mbox{\rm if\ } j \equiv
\ell \mbox{\rm \, mod}(k+1),\\ -1 & \mbox{\rm if\ } j \equiv 0
\mbox{\rm \, mod}(k+1),\\0 & \mbox{\rm otherwise}.
\end{array} \right.
\end{equation}
\end{theorem}

To prove the theorem we will need the following lemma.

\begin{lemma} \label{lem:1} Let $m$ and $n$ be positive integers,
and $m=q_1^{\ell_1} q_2^{\ell_2}\dots  q_r^{\ell_r}$, $1 \le \ell_i \le
k$, be the factorization of $m$ to powers of $k$-prime numbers. Let,
moreover, $\nu_j\ge 1$ be the maximal power of $k$-prime $q_j$
dividing $n$, $j=1,\dots ,r$. Then $m {| \atop k} n$ if and only if
\begin{equation} \label{eq:20}
\nu_j\ge \ell_j, \quad \nu_j \equiv \ell_j, \ell_j+1,\dots ,k \mbox{\rm
\, mod}(k+1), \ j=1,2,\dots ,r.
\end{equation}
\end{lemma}

\proof Denote by $i_j$ the maximal power of $q_j^{k+1}$ dividing
$n$, $j=1,2,\dots ,r$. Notice that $q_j^{\ell_j} {| \atop k} n$ if and
only if
$$q_j^{\ell_j} \, \bigg| \, \frac{n}{\left( q_j^{k+1}\right)^{i_j}}.$$
Thus $q_j^{\ell_j} {| \atop k} n$ if and only if
$q_j^{(k+1)i_j+\ell_j}|n$. Since $1 \le \ell_j \le k$, $$\nu_j \in
\left[(k+1)i_j+\ell_j,(k+1) i_j+k \right], \ j=1,2,\dots ,r.$$ Indeed,
increasing $ \nu_j$ we violate the assumption about maximality of
$i_j$. \qed

%
%
%Notice that $i_j \ge 0$. Let $q_j=p_j^{(k+1)^{m_j}}$, where $p_j$ is
%a (conventional) prime, $j=1,2,\dots ,r$. Let furthermore, by
%(\ref{eq:1}) and (\ref{eq:2}),
%$$p_j^{\sum_{i \ge 0} a_i (k+1)^i}\|n.$$
%Since $$\left(q_j^{k+1}\right)^{i_j}=p_j^{i_j(k+1)^{m_j+1}} \,\bigg|
%\, n,$$ but
%$$\left(q_j^{k+1}\right)^{i_j+1} \not\bigg| \, n,$$
%we have $i_j=a_{m_j+1}$. Therefore, since $q_j^{\ell_j}=p_j^{\ell_j
%(k+1)^{m_j}}$, we conclude that $q_j^{\ell_j} {| \atop k} n$ if and
%only if $\ell_j \le a_{m_j}$, or
%$$q_j^{\ell_j} \, \bigg| \, \frac{n}{\left( q_j^{k+1}\right)^{i_j}}.$$
%Thus $q_j^{\ell_j} {| \atop k} n$ if and only if
%$q_j^{(k+1)i_j+\ell_j}|n$. Therefore, $\nu_j \in
%\left[(k+1)i_j+\ell_j,(k+1) i_j+k \right]$. Indeed, increasing $
%\nu_j$ we violate the assumption about maximality of $i_j$. \qed


\noindent
{\it Proof of Theorem \ref{thm:1}.}\ Let $x$ be a positive real.
Consider all possible collections of $r$ non-negative integers
$\alpha_1, \alpha_2,\dots ,\alpha_r$, satisfying $q_1^{\alpha_1}
q_2^{\alpha_2}\dots  q_r^{\alpha_r} \le x$. Let us partition the
sequence $1,2,\dots ,\lfloor x \rfloor$ into non-intersecting classes
$T_{\alpha_1,\dots ,\alpha_r}$ according to the rule:

\noindent $h \in T_{\alpha_1,\dots ,\alpha_r}$ if $$\max \left\{
\tau\ge 0:\, q_i^{\tau} {| \atop k} h \right\}=\alpha_i, \quad
i=1,2,\dots ,r.$$ Using inclusion-exclusion for the cardinalities of
the classes we obtain
$$\left| T_{\alpha_1,\dots ,\alpha_r}\right|=\lfloor \lambda \rfloor
-\sum_{1\le i \le r} \left\lfloor \frac{\lambda}{q_i} \right\rfloor
+\sum_{1\le i < j \le r} \left\lfloor \frac{\lambda}{q_i q_j}
\right\rfloor-$$
\begin{equation} \label{eq:21}
-\sum_{1\le i < j <\ell\le r} \left\lfloor \frac{\lambda}{q_i q_j
q_\ell} \right\rfloor+\dots +(-1)^r \left\lfloor \frac{\lambda}{q_1
q_2\dots  q_r} \right\rfloor,
\end{equation}
where $$\lambda=\frac{x}{q_1^{\alpha_1}
q_2^{\alpha_2}\dots  q_r^{\alpha_r}}.$$ By Lemma \ref{lem:1}, $m {|
\atop k} q_1^{\alpha_1} q_2^{\alpha_2}\dots  q_r^{\alpha_r}$ if and only
if $\alpha_j \equiv \ell_j, \ell_j+1,\dots ,k \mbox{\rm \, mod}(k+1)$,
$j=1,2,\dots ,r$. Therefore,
\begin{equation} \label{eq:22}
\left\lfloor \frac{x}{m} \right\rfloor^{(k)}=\sum_{\alpha_j \equiv
\ell_j, \ell_j+1,\dots ,k \mbox{\rm \scriptsize \, mod}(k+1),\,
j=1,2,\dots ,r} \left| T_{\alpha_1,\dots ,\alpha_r}\right|. \end{equation}
Specifically, let us consider the summands with $\ell_j \le \alpha_j
\le k+1$ (other groups of summands $\mbox{\rm \, mod}(k+1)$ are
considered analogously). Let us correspond to every summand of form
$\left\lfloor \frac{\lambda}{q_{i_1} q_{i_2}\ldots
q_{i_s}}\right\rfloor$ in (\ref{eq:21}) the monomial $x_1^{\alpha_1}
x_2^{\alpha_2} \ldots x_r^{\alpha_r} \cdot$ $x_{i_1} x_{i_2} \ldots
x_{i_s}$. Clearly it is a one-to-one correspondence. Assuming that
for a linear combination of summands we correspond the same linear
combination of the images, we find that to $\left|T_{\alpha_1,
\ldots, \alpha_r} \right|$, see (\ref{eq:21}), corresponds the
polynomial
$$P_{\alpha_1,\ldots,\alpha_r}(x_1,\ldots,x_r)=x_1^{\alpha_1}
x_2^{\alpha_2} \ldots x_r^{\alpha_r} \sum_{s=0}^r (-1)^s \prod_{1
\le i_1 < i_2 < \ldots < i_s \le r} x_{i_1} x_{i_2} \ldots
x_{i_s},$$ and to the considered subsum of (\ref{eq:22}) corresponds
the polynomial
$$R(x_1,\ldots, x_r)=\sum_{\alpha_j=\ell_j,\ell_j+1,\ldots,k;
j=1,2,\ldots, r} x_1^{\alpha_1} x_2^{\alpha_2} \ldots x_r^{\alpha_r}
\cdot$$  \begin{equation} \label{eq:R} \cdot \sum_{s=0}^r (-1)^s
\prod_{1 \le i_1 < i_2 < \ldots < i_s \le r} x_{i_1} x_{i_2} \ldots
x_{i_s}.
\end{equation}
The statement of the theorem is true if we manage to prove that
\begin{equation} \label{eq:R+1}
R(x_1,\ldots, x_r)=\sum_{\ell_1 \le i_1 \le k+1} \sum_{\ell_2 \le
i_2 \le k+1} \ldots \sum_{\ell_r \le i_r \le k+1}
\left(\prod_{s=1}^r a_{i_s}^{(\ell_s)} \right) x_1^{i_1} x_2^{i_2}
\ldots x_r^{i_r}.
\end{equation}
Since
$$\sum_{s=0}^r (-1)^s \prod_{1 \le i_1 < i_2 < \ldots < i_s \le r} x_{i_1} x_{i_2} \ldots
x_{i_s} =\prod_{j=1}^r (1-x_j),$$ we find from (\ref{eq:R}) that
$$R(x_1,\ldots,x_r)=\prod_{j=1}^r \sum_{\alpha_j=\ell_j}^k
(x_j^{\alpha_j}-x_j^{\alpha_j+1})=\prod_{j=1}^r
(x_j^{\ell_j}-x_j^{k+1}),$$ and (\ref{eq:R+1}) follows. \qed


%From constraints on the summation in (\ref{eq:22}) it follows that
%the summand of the form $\left\lfloor \frac{x}{q_1^{\alpha_1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor$ is not canceled in
%(\ref{eq:22}) if and only if all $\alpha_j \equiv 0$ or $\alpha_j
%\equiv \ell_j \mbox{\rm \, mod}(k+1).$ Indeed, if for example
%$\alpha_1=r,$ $1 \le r \le \ell_j-1$, then along with $\left\lfloor
%\frac{x}{q_1^{\alpha_1} q_2^{\alpha_2}\dots q_r^{\alpha_r}}
%\right\rfloor$ in the second sum of (\ref{eq:21}) appears
%$$-\left\lfloor \frac{\left\lfloor \frac{x}{q_1^{\alpha_1-1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor}{q_1}
%\right\rfloor=-\left\lfloor \frac{x}{q_1^{\alpha_1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor.$$ However, when
%$\alpha_1 \equiv 0 \mbox{\rm \, mod}(k+1)$, then only the term
%$$-\left\lfloor \frac{\left\lfloor \frac{x}{q_1^{\alpha_1-1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor}{q_1}
%\right\rfloor=-\left\lfloor \frac{x}{q_1^{\alpha_1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor$$ appears, without
%its positive counterpart. When $\alpha_1 \equiv \ell_1 \mbox{\rm \,
%mod}(k+1)$ then only the term
%$$+\left\lfloor \frac{x}{q_1^{\alpha_1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor$$ appears, since in
%the second sum of (\ref{eq:21}) in the range of summation of
%(\ref{eq:22}) there is no summand
%$$-\left\lfloor \frac{\left\lfloor \frac{x}{q_1^{\alpha_1-1}
%q_2^{\alpha_2}\dots q_r^{\alpha_r}} \right\rfloor}{q_1}
%\right\rfloor.$$ Therefore (\ref{eq:22}) evidently yields
%(\ref{eq:18}) with the numbers $a_j^{(\ell)}$ (\ref{eq:19}). \qed

\begin{example} {\rm Let $k=2$, $m=12$, $x=100$. Then $q_1=2$, $q_2=3$,
$\ell_1=2$, $\ell_2=1$, and by (\ref{eq:18}) we have
$$\left\lfloor \frac{100}{12} \right\rfloor^{(2)}=\sum_{j_1 \ge 2}
\sum_{j_2 \ge 1} a_{j_1}^{(2)} a_{j_2}^{(1)} \left\lfloor
\frac{100}{2^{j_1} 3^{j_2} } \right\rfloor,$$ where
$$a_{j_1}^{(2)} =\left\{ \begin{array}{rl} 1, & \mbox{\rm if\ } j_1
\equiv 2 \mbox{\rm \, mod\,}3\\
 -1, & \mbox{\rm if\ } j_1
\equiv 0 \mbox{\rm \, mod\,}3\\
0, & \mbox{\rm otherwise} \end{array} \right. $$ and
$$a_{j_2}^{(1)} =\left\{ \begin{array}{rl} 1, & \mbox{\rm if\ } j_2
\equiv 1 \mbox{\rm \, mod\,}3\\
 -1, & \mbox{\rm if\ } j_2
\equiv 0 \mbox{\rm \, mod\,}3\\
0, & \mbox{\rm otherwise} \end{array} \right. $$ Therefore, we have
$$ \renewcommand{\arraystretch}{2.0}
\begin{array}{lll}
\left\lfloor \frac{100}{12} \right\rfloor^{(2)}&=&a_2^{(2)}
a_1^{(1)} \left\lfloor \frac{100}{2^2 3} \right\rfloor+a_3^{(2)}
a_1^{(1)} \left\lfloor \frac{100}{2^3 3} \right\rfloor+a_4^{(2)}
a_1^{(1)} \left\lfloor \frac{100}{2^4 3} \right\rfloor\\
&&+a_5^{(2)}
a_1^{(1)} \left\lfloor \frac{100}{2^5 3} \right\rfloor+a_2^{(2)}
a_2^{(1)} \left\lfloor \frac{100}{2^2 3^2} \right\rfloor+a_3^{(2)}
a_2^{(1)} \left\lfloor \frac{100}{2^3 3^2} \right\rfloor\\
&=&\left\lfloor \frac{100}{2^2 3} \right\rfloor-\left\lfloor
\frac{100}{2^3 3} \right\rfloor+\left\lfloor \frac{100}{2^5 3}
\right\rfloor\\
&=&8-4+1=5.
\end{array}
$$ 
Indeed, we have five numbers not exceeding
$100$, which are $2$-multiples of $12$: $12, 36, 60, 84,$ $96$. \qed
}\end{example}

Notice that when $x=n$, the value $\left\lfloor \frac{n}{m}
\right\rfloor^{(k)}$ is a complicated arithmetic function in two
variables which, in contrast to the conventional function
$\left\lfloor \frac{n}{m} \right\rfloor=\left\lfloor \frac{n}{m}
\right\rfloor^{(\infty)}$, is not homogeneous, i.e., in general
$\left\lfloor \frac{n}{m} \right\rfloor^{(k)} \neq \left\lfloor
\frac{nt}{mt} \right\rfloor^{(k)}$.

\begin{example} \label{ex:3} {\rm Though
$\frac{25}{3}=\frac{50}{6}=\frac{600}{72}=\frac{100}{12}=\frac{300}{36},$
we have \begin{eqnarray*} \label{eq:23} \left\lfloor \frac{25}{3}
\right\rfloor^{(2)}=8, \left\lfloor \frac{50}{6}
\right\rfloor^{(2)}=7, \left\lfloor \frac{600}{72}
\right\rfloor^{(2)}=6, \left\lfloor \frac{100}{12}
\right\rfloor^{(2)}=5, \left\lfloor \frac{300}{36}
\right\rfloor^{(2)}=4.\end{eqnarray*} }
\end{example}

The question about the minimum of $\left\lfloor \frac{nt}{mt}
\right\rfloor^{(k)}$ in $t$ is an interesting open problem in
$k$-arithmetics.

\subsection{Asymptotic Formula for $\left\lfloor
\frac{x}{m} \right\rfloor^{(k)}$}

\begin{theorem} \label{thm:2} a) If $m=q_1^{\ell_1}
q_2^{\ell_2}\dots q_r^{\ell_r}$, $1 \le \ell_i \le k$, $q_i \in
Q^{(k)},$ then \begin{equation} \label{eq:24} \left\lfloor
\frac{x}{m} \right\rfloor^{(k)}=x \prod_{i=1}^r
\frac{q_i^{k+1-\ell_i}-1}{q_i^{k+1}-1}+\theta \ln^r \,x,
\end{equation}
such that
$$|\theta| \le \prod_{i=1}^r \frac{1}{\ln \, q_i}.$$

\noindent
b) For any $\varepsilon>0$ there exists a constant $a_\varepsilon>0$
depending only on $\varepsilon$, such that uniformly in $m \le x$
the following inequality holds:
\begin{equation} \label{eq:25}
\left| \left\lfloor \frac{x}{m} \right\rfloor^{(k)}-x \prod_{i=1}^r
\frac{q_i^{k+1-\ell_i}-1}{q_i^{k+1}-1} \right| \le a_\varepsilon
x^\varepsilon .
\end{equation}

\end{theorem}


\proof a) Omitting in the right-hand side of (\ref{eq:18}) the floor
function and taking into account that by (\ref{eq:19}),
\begin{equation} \label{eq:26}
\sum_{j \ge \ell} a_j^{(\ell)} \frac{1}{q^j}=\sum_{i \ge 1} \left(
\frac{1}{q^{(k+1)(i-1)+\ell}}-\frac{1}{q^{(k+1)i}}\right)=\frac{q^{k+1-\ell}-1}{q^{k+1}-1},
\end{equation}
we obtain instead of the right-hand side of (\ref{eq:18}) the
following value:
$$x \prod_{i=1}^r \frac{q_i^{k+1-\ell_i}-1}{q_i^{k+1}-1}.$$
The remainder in (\ref{eq:24}) is an evident estimate for the number
of non-zero summands in (\ref{eq:18}).

\noindent b) Notice that the number of divisors $m$ is at least
$2^r$, which, by the Wiman-Ramanujan theorem (see e.g.
\cite{prac78}), for large enough $n>n_\delta$ does not exceed
\begin{equation} \label{eq:WR}
2^{(1+\delta)\frac{\ln x}{\ln \ln x}}
\end{equation}
 uniformly in $m \le x$.
Therefore,
\begin{equation} \label{eq:27}
r \le (1+\delta) \frac{\ln x}{\ln \ln x}.
\end{equation}
Furthermore, the number of non-zero summands in the right-hand side
of (\ref{eq:18}) does not exceed the number of solutions in natural
numbers $k_1, k_2, \dots , k_r$ of the inequality
\begin{equation} \label{eq:28}
\prod_{i=1}^r 2^{k_i} \le x,
\end{equation}
or, which is the same, the number of solutions to the inequality
\begin{equation} \label{eq:29}
k_1+k_2+\dots +k_r \le \lfloor \log_2 x \rfloor .
\end{equation}

Denote by $c(r,n)$ the number of compositions of $n$ with exactly
$r$ parts. It is well known \cite{andr76} that $c(r,n)={n-1 \choose
r-1}$. Therefore, the number $N_x$ of solutions to (\ref{eq:29}) is
\small
\begin{equation}
%N_x=
\sum_{i=1}^{\lfloor \log_2 x \rfloor} c(r,i)=\sum_{i=1}^{\lfloor
\log_2 x \rfloor} {i-1 \choose r-1}={\lfloor \log_2 x \rfloor +1 \choose
r}-\delta_{r,1} %\le $$ 
%\begin{equation} \label{eq:30}
\le {\lfloor \log_2 2x \rfloor \choose r} \le {\lfloor \log_2 2x
\rfloor \choose (1+\delta) \frac{\ln x}{\ln \ln x}},
\end{equation}
\normalsize
where the last inequality follows from (\ref{eq:27}). Now using the
Stirling approximation we obtain
\begin{equation} \label{eq:astast}
N_x \le x^{\frac{\ln \ln \ln x}{\ln \ln x}} (1+o(x)).\end{equation}
Therefore, for $x>x_\varepsilon$,
\begin{equation} \label{eq:31}
N_x \le x^\varepsilon.
\end{equation}
It is only left to choose the constant $a_\varepsilon$ in such a way
that (\ref{eq:31}) will hold as well for $x\le x_\varepsilon$. \qed

\begin{remark}{\rm
It is known \cite{prac78} that estimate (\ref{eq:WR}) cannot be
essentially improved, i.e. there are infinitely many $n \le x$ for
which the number of divisors exceeds $2^{(1-\delta) \frac{\ln x}{\ln
\ln x}}$. Let us show that also in the case $k < \infty$,
(\ref{eq:WR}) cannot be essentially improved when $k$-divisors are
used instead of the conventional divisors.

Indeed, $\prod_{p \le N, p \in \mathbf{P}} p \sim e^{N+o(N)}$. Let
us consider the most distinct from the conventional case $k=1$. For
$r$ large enough consider $n =\prod_{p \le p_r} p$. We have
$$n \le e^{p_r (1+\varepsilon)} \Rightarrow p_r \ge \frac{\ln
n}{1+\varepsilon}, \quad r \ge \pi \left(\frac{\ln n}{1+\varepsilon}
\right) \ge \frac{\frac{\ln n}{1+\varepsilon} (1-\varepsilon)}{\ln
\ln n-\ln (1+\varepsilon)}.$$ Therefore, for $2^r$ divisors of $n$
(coinciding with $1$-divisors) we have
$$2^r \ge 2^{\frac{(\ln n) (1-2 \varepsilon)}{\ln \ln
n-\ln(1+\varepsilon)}} \le 2^{(1-\delta) \frac{\ln n}{\ln \ln n}}$$
for a relevant small enough $\delta$. It is easy to check that
(\ref{eq:astast}) cannot be essentially improved by a more accurate
estimate of the number of summands in the right-hand side of
(\ref{eq:18}), i.e., the number
\begin{equation} \label{eq:astastast}
k_1 \ln q_1+\cdots + k_r \ln q_r \le \lfloor \ln x \rfloor,
\end{equation}
instead of the estimate (\ref{eq:28}). It is known \cite{beuk75}
that the number of solutions to (\ref{eq:astastast}) in natural
numbers is $O\left(\frac{\ln^r x}{r! \prod_{i \le r} \ln q_i}
\right)$. This by more cumbersome calculations using (\ref{eq:27})
also yields (\ref{eq:astast}).
 \qed }
\end{remark}


\begin{example} \label{ex:4} {\rm The obtained asymptotics provide accurate enough
estimates even for small numbers. For example, using the main term
(\ref{eq:25}), we get (with rounding)
$$ \left\lfloor \frac{25}{3}
\right\rfloor^{(2)}=7.7, \left\lfloor \frac{50}{6}
\right\rfloor^{(2)}=6.6, \left\lfloor \frac{600}{72}
\right\rfloor^{(2)}=5.7, \left\lfloor \frac{100}{12}
\right\rfloor^{(2)}=4.4, \left\lfloor \frac{300}{36}
\right\rfloor^{(2)}=3.3. $$ This can be compared to the exact values
$8, 7, 6, 5$, and $4$ appearing in Example \ref{ex:3}. \qed
}\end{example}


\section{A $k$-analog of the Euler Function} \label{sec:totient}

Let us consider a $k$-analog of the Euler function in
$k$-arithmetics:
\begin{equation} \label{eq:32}
\varphi_k(n)=\sum_{1\le j \le n: (j,n)_k=1} \ 1.
\end{equation}

\begin{example} \label{ex:5} {\rm It is easy to check that
$$\varphi_1(100)=77, \varphi_2(100)=46, \varphi_3(100)=43,
\varphi_4(100)=42, \varphi_5(100)=41,$$ and $\varphi_k(100)=40$ for
$k \ge 6$. }
\end{example}

Notice that it is convenient considering the Euler function along
with the more general function
\begin{equation} \label{eq:34}
\varphi_k(x,n)=\sum_{1 \le j \le x: (j,n)_k=1} \ 1,
\end{equation}
such that $\varphi_k(n)=\varphi_k(n,n)$.

\begin{theorem} \label{thm:3}
\begin{equation} \label{eq:35}
\varphi_k(x,n)=\sum_{d {\tiny {| \atop k}} n} \mu_k(d) \left\lfloor
\frac{x}{d} \right\rfloor^{(k)}.
\end{equation}
\end{theorem}

\begin{remark} {\rm  Consider a structurally
close to $\varphi(n)$, but not having a clear arithmetic sense,
multiplicative function
\begin{equation} \label{eq:36}
\tilde{\varphi}_k(n)=\sum_{d {\tiny {| \atop k}} n} \mu_k(d)
\frac{n}{d}.
\end{equation}

Notice, that in contrast to $\tilde{\varphi}_k(n)$ the function
$\varphi_k(n)$ is not multiplicative. In particular the equality
$$\sum_{d {\tiny {| \atop k}} n} \varphi_k(d)=n,$$ is not valid
here (though is correct for (\ref{eq:36})). Therefore, and as well
since $\left\lfloor \frac{n}{d} \right\rfloor^{(k)}$ is not a
function of the ratio $\frac{n}{d}$, apparently there is no way to
use here the $k$-analog of the M\"{o}bius inversion:
$$\sum_{d {\tiny {| \atop k}} n} f(d)=F(n) \Rightarrow \sum_{d {\tiny {| \atop k}} n}
\mu_k(d) F \left( \frac{n}{d} \right)=f(n).$$ Moreover, it follows
from (\ref{eq:36}) that
\begin{equation} \label{eq:36a}
\tilde{\varphi}_k(n)=n \prod_{q {\tiny {| \atop k}} n, \, q \in
Q^{(k)}} \ \left( 1-\frac{1}{q} \right).
\end{equation}
We will see later that this means that $\tilde{\varphi}_k(n)$ even
 asymptotically  does not approximate $\varphi_k(n)$. Nevertheless we
will demonstrate that $\varphi_k(n)$ is accurately approximated by
some simple enough multiplicative function. 
  }
\end{remark}

\noindent
{\it Proof of Theorem 3.} For every fixed $n$ let us consider the
$k$-multiplicative function $\lambda_n^{(k)}(m)$ defined on the powers of
$k$-primes as
$$ \lambda_n^{(k)}(q^\ell)=\left\{\begin{array}{ll}1, & \mbox{\rm if\ }
q^\ell {\tiny {| \atop k}} n;\\
0, & \mbox{\rm otherwise,} \end{array} \ \ 1 \le \ell \le
k.\right.$$ Then for every $m \le n$ we have
\begin{equation} \label{eq:37}
\lambda_n^{(k)}(m)=\left\{\begin{array}{ll}1, & \mbox{\rm if\ }
m {\tiny {| \atop k}} n;\\
0, & \mbox{\rm otherwise.} \end{array} \right.
\end{equation}
It follows from (\ref{eq:34}) and (\ref{eq:37}) that
\begin{equation} \label{eq:38}
\varphi_k(x,n)=\sum_{1 \le j \le x} \prod_{q {\tiny {| \atop k}} n}
\left(1-\lambda_j^{(k)}(q) \right).
\end{equation}
Indeed, if there is no $k$-prime, which simultaneously $k$-divides
$n$ and $k$-divides $j$, then $(j,n)_k=1$ and
$$\prod_{q {\tiny {| \atop k}} n}\left(1-\lambda_j^{(k)}(q) \right)
=1.$$ If there is at least one $k$-prime $q$ that $k$-divides
simultaneously $n$ and $j$, then
$$\prod_{q {\tiny {| \atop k}} n}\left(1-\lambda_j^{(k)}(q) \right)
=0.$$ This gives (\ref{eq:38}). Let us rewrite now (\ref{eq:9}) for
$\theta(d)=\lambda_j^{(k)}(d)$. We have
\begin{equation} \label{eq:39}
\prod_{q {\tiny {| \atop k}} n}\left(1-\lambda_j^{(k)}(q)
\right)=\sum_{d {\tiny {| \atop k}} n} \mu_k(d) \lambda_j^{(k)}(d).
\end{equation}
We deduce from (\ref{eq:38}) and (\ref{eq:39})
\begin{equation} \label{eq:40}
\varphi_k(x,n)=\sum_{1 \le j \le x} \sum_{d {\tiny {| \atop k}}
n}\mu_k(d) \lambda_j^{(k)}(d)=\sum_{d {\tiny {| \atop k}} n}
\mu_k(d)\sum_{1 \le j \le x}  \lambda_j^{(k)}(d).
\end{equation}
However, it follows from (\ref{eq:37}) that
\begin{equation} \label{eq:41}
\sum_{1 \le j \le x}  \lambda_j^{(k)}(d)=\left\lfloor \frac{x}{d}
\right\rfloor^{(k)},
\end{equation}
and (\ref{eq:40}) and (\ref{eq:41}) yield (\ref{eq:35}). \qed

Now we are in a position to present an explicit expression for
$\varphi_k(n)$.

\begin{theorem} \label{thm:4}
Let $q_1, q_2, \dots , q_r,$ be all $k$-prime $k$-divisors of $n$. Then
\begin{equation} \label{eq:42}
\varphi_k(x,n)=\sum (-1)^{\tau_1+\tau_2+\dots +\tau_r} \left\lfloor
\frac{x}{q_1^{t_1} q_2^{t_2} \dots  q_r^{t_r}}\right\rfloor,
\end{equation}
where the summation is over all non-negative $t_1, t_2, \dots , t_r,$
for which $t_i \equiv 0 \mbox{\rm \, mod}(k+1)$ or $t_i \equiv 1
\mbox{\rm \, mod}(k+1)$, and
\begin{equation} \label{eq:43}
\tau_i=\left\{\begin{array}{ll} 0, & \mbox{\rm if\ }  t_i \equiv 0
\mbox{\rm \, mod}(k+1),\\
1, & \mbox{\rm if\ }  t_i \equiv 1 \mbox{\rm \, mod}(k+1),
\end{array} \right.
\end{equation}
$i=1,2,\dots ,r$.
\end{theorem}

\proof According to Theorem \ref{thm:3} it is sufficient to consider
the divisors of $n$ having the form $d=q_{i_1} q_{i_2}\dots q_{i_h}$,
$1 \le i_1< i_2<\dots <i_h \le r$. By Theorem \ref{thm:1} in this case
\begin{equation} \label{eq:44}
\left\lfloor \frac{x}{d}\right\rfloor^{(k)}=\sum_{j_1 \ge 1}
\sum_{j_2 \ge 1} \dots  \sum_{j_h \ge 1} \left(\prod_{i=1}^h
a_{j_i}^{(1)} \right) \left\lfloor \frac{x}{q_{i_1}^{j_1}
q_{i_2}^{j_2}\dots q_{i_h}^{j_h}} \right\rfloor,
\end{equation}
where
\begin{equation} \label{eq:45}
a_j^{(1)}=\left\{ \begin{array}{rl}  1, & \mbox{\rm if\ }  j \equiv
1 \mbox{\rm \, mod}(k+1), \\
-1, & \mbox{\rm if\ }  j \equiv 0 \mbox{\rm \, mod}(k+1),\\
0, & \mbox{\rm otherwise.}
\end{array} \right.
\end{equation}

Set
\begin{equation} \label{eq:46}
\theta(j)=\left\{\begin{array}{ll} 0, & \mbox{\rm if\ }  j\equiv 0
\mbox{\rm \, mod}(k+1),\\
1, & \mbox{\rm if\ } j \equiv 1 \mbox{\rm \, mod}(k+1).
\end{array} \right.
\end{equation}
Then by (\ref{eq:44})-(\ref{eq:45}) we have
$$\left\lfloor \frac{x}{d} \right\rfloor^{(k)}=\sum (-1)^{\theta(j_1)+
\theta(j_2)+\dots +\theta(j_h)+h} \left\lfloor \frac{x}{q_{i_1}^{j_1}
q_{i_2}^{j_2}\dots q_{i_h}^{j_h}} \right\rfloor,$$ where the summation
is over all $j_i \ge 1$ for which $j_i \equiv 0 \mbox{\rm \,
mod}(k+1)$ or $j_i \equiv 1 \mbox{\rm \, mod}(k+1)$. Hence for
$d=q_{i_1} q_{i_2}\dots q_{i_h}$,
$$\mu_k(d)\left\lfloor \frac{x}{d} \right\rfloor^{(k)}=\sum (-1)^{\theta(j_1)+
\theta(j_2)+\dots +\theta(j_h)} \left\lfloor \frac{x}{q_{i_1}^{j_1}
q_{i_2}^{j_2}\dots q_{i_h}^{j_h}} \right\rfloor.$$ By Theorem
\ref{thm:3} then
\begin{equation} \label{eq:47}
\varphi_k(x,n)=\sum_{1 \le i_1 < i_2 < \dots  <i_h \le r} \quad \sum
(-1)^{\theta(j_1)+ \theta(j_2)+\dots +\theta(j_h)} \left\lfloor
\frac{x}{q_{i_1}^{j_1} q_{i_2}^{j_2}\dots q_{i_h}^{j_h}} \right\rfloor,
\end{equation}
where the internal summation is over all $j_i \ge 1$ satisfying
either $j \equiv 0 \mbox{\rm \, mod}(k+1)$ or $j \equiv 1 \mbox{\rm
\, mod}(k+1)$. Clearly (\ref{eq:42}) follows from (\ref{eq:47}) and
(\ref{eq:46}). \qed

\begin{example} \label{ex:6} {\rm For $n=x=100$ ($r=2$, $q_1=2, q_2=5$)
we have by (\ref{eq:42}) and (\ref{eq:43}),
$$\varphi_2(100)=\sum_{t_1 \ge 0, \,
t_1 \equiv 0 \mbox{\rm \scriptsize \,or\,} 1  \mbox{\rm \scriptsize
\,mod\,}3} \quad \sum_{t_2 \ge 0, \, t_2 \equiv 0 \mbox{\rm
\scriptsize \,or\,} 1  \mbox{\rm \scriptsize \,mod\,}3}
(-1)^{\tau_1+\tau_2} \left\lfloor \frac{100}{2^{t_1} 5^{t_2}}
\right\rfloor=$$
$$=100-\frac{100}{2}+\left\lfloor \frac{100}{8} \right\rfloor-
\left\lfloor \frac{100}{16} \right\rfloor+\left\lfloor
\frac{100}{64} \right\rfloor-$$
$$-\frac{100}{5}+\frac{100}{2 \cdot 5}-\left\lfloor \frac{100}{8 \cdot 5}
\right\rfloor+\left\lfloor \frac{100}{16 \cdot 5}
\right\rfloor=46.$$
}
\end{example}

Now we treat the asymptotic behavior of $\varphi_k(n)$.

\begin{theorem} \label{thm:5}
\begin{equation} \label{eq:48}
\varphi_k(x,n)=\kappa_k(n) x +O \left( (nx)^\varepsilon \right),
\end{equation}
where
\begin{eqnarray*} \label{eq:48'}
\kappa_k(n)=\prod_{q{| \atop k}n}
\left(1+\frac{1}{q}+\dots +\frac{1}{q^k} \right)^{-1},
\end{eqnarray*}
and the implied constant only depends on $\varepsilon$.
\end{theorem}

\proof Set
\begin{equation} \label{eq:49}
n^\ast=\prod_{q{| \atop k}n} \frac{q^{k+1}-1}{q^k-1}.
\end{equation}
Using Theorem \ref{thm:3} and the uniform estimate (\ref{eq:25}) for
$\ell_i=1$, $i=1,2,\dots ,r$, we find
$$\left| \varphi_k(x,n)-x \sum_{d{| \atop k}n} \frac{\mu_k(d)}{d^\ast}
\right|=\left| \sum_{d{| \atop k}n} \mu_k(d) \left(\left\lfloor
\frac{x}{d} \right\rfloor^{(k)}-\frac{x}{d^\ast} \right) \right| \le
$$
\begin{equation} \label{eq:50}
\le  \sum_{d{| \atop k}n}  \left| \left\lfloor \frac{x}{d}
\right\rfloor^{(k)}-\frac{x}{d^\ast} \right| \le a_\varepsilon
x^\varepsilon \sum_{d{| \atop k}n} 1= a_\varepsilon x^\varepsilon
\tau^{(k)}(n) \le a_\varepsilon x^\varepsilon \tau(n),
\end{equation}
where $\tau^{(k)}(n)$ is the number of $k$-divisors of $n$, and
$\tau(n)$ is the number of conventional divisors of $n$. By the
Wiman-Ramanujan theorem (see e.g. \cite{prac78}) for $\delta>0$ and
$n > n_0(\delta)$,
$$\tau(n) < n^{\frac{(1+\delta) \ln 2}{\ln \ln n}} < n^\varepsilon,
\quad n \ge n_\varepsilon.$$ By (\ref{eq:50}) and (\ref{eq:48}) this
means that it is sufficient to demonstrate that
\begin{equation} \label{eq:51}
\sum_{d{| \atop k}n} \frac{\mu_k(d)}{d^\ast}=\prod_{q{| \atop k}n}
\left(1+\frac{1}{q}+\dots +\frac{1}{q^k} \right)^{-1}.
\end{equation}
This easily follows from (\ref{eq:9}) if one sets
$\theta(n)=\left(n^\ast\right)^{-1}$. \qed

Theorem \ref{thm:5} is a generalization of the main result of
\cite{shev81} which can be deduced from it setting $k=1$, $x=n$. As
well Theorem 14 of \cite{cohe93} is a particular case of our theorem
when $k=1$.

Notice that for the values $\varphi_k(n)$ presented in Example
\ref{ex:5}, using the main term (\ref{eq:48}) for $x=n$ we obtain
the following approximations: $\varphi_1(100) \approx 76.9$ (the
exact value $77$), $\varphi_2(100) \approx 46.1 (46)$,
$\varphi_3(100) \approx 42.7 (43)$, $\varphi_4(100) \approx 41.3
(42)$, $\varphi_5(100) \approx 40.6 (41)$, and $\varphi_k(100)
\approx 40.3 (40)$ for $k \ge 6$. Thus the approximation is quite
accurate even for small $n$'s.

\section{Sums of the Values of the $k$-Euler Function} \label{sec:sums}

The following double summation formula due to Mertens (see e.g.
\cite{finc03}) is well known:
\begin{equation} \label{eq:52}
\sum_{i=1}^n \varphi(i)=\frac{3}{\pi^2}n^2+O(n \ln n).
\end{equation}
Consider $\sum_{i=1}^n \varphi_k(n)$. We will need an estimate for
the following sum:
\begin{equation} \label{eq:53}
\nu_k(x,d)=\sum_{1 \le i \le x:d{| \atop k}i} i
\end{equation}
for the numbers of the form
\begin{equation} \label{eq:54}
d=q_1 q_2 \dots q_r, \quad q_1<q_2<\dots <q_r, \quad q_i \in Q^{(k)},
i=1,2,\dots ,r.
\end{equation}

\begin{lemma} \label{lem:2}
Let $d$ be of the form (\ref{eq:54}). Then for any $\varepsilon>0$
there exists a $b_\varepsilon>0$, such that
\begin{equation} \label{eq:55}
\left|\nu_k(x,d)-\frac{x^2}{2d^\ast} \right| \le b_\varepsilon
x^{1+\varepsilon},
\end{equation}
where
\begin{equation} \label{eq:56}
d^\ast=\prod_{i=1}^r \frac{q_i^{k+1}-1}{q_i^k-1}.
\end{equation}
\end{lemma}

\proof By (\ref{eq:25}) when $\ell_i=1$ uniformly in $d \le x$ we
have
\begin{equation} \label{eq:57}
\left\lfloor \frac{x}{d} \right\rfloor^{(k)}=\sum_{1 \le i \le x:d{|
\atop k}i}  1=\frac{x}{d^\ast}+O(x^\varepsilon).
\end{equation}
Using the Stieltjes integration with the integrator $\left\lfloor
\frac{x}{d} \right\rfloor^{(k)}$ (assuming $d$ is a constant) we
obtain the sought results from (\ref{eq:57}). \qed

\begin{theorem} \label{thm:6}
We have for any $\varepsilon>0$,
$$\sum_{n \le x} \varphi_k(n)=\frac{x^2}{2} \prod_{q \in Q^{(k)}}
\left(1-\left(\frac{q^k-1}{q^{k+1}-1} \right)^2
\right)+o(x^{1+\varepsilon}).$$
\end{theorem}

\proof Using (\ref{eq:35}) and (\ref{eq:57}) for $x=n$ we find
$$\sum_{n \le x} \varphi_k(n)=\sum_{n \le x} \sum_{d{|
\atop k}n} \mu_k(d) \left\lfloor \frac{n}{d} \right\rfloor^{(k)}=$$
$$=\sum_{n \le x} n \sum_{d{| \atop k}n}
\frac{\mu_k(d)}{d^\ast}+o(x^{1+\varepsilon})=\sum_{d \le x}
\frac{\mu_k(d)}{d^\ast} \sum_{n \le x:\,d{| \atop k}n}n
+o(x^{1+\varepsilon}).$$ From Lemma \ref{lem:2} now we get
$$\sum_{n \le x} \varphi_k(n)=\sum_{d \le x} \frac{\mu_k(d)}{d^\ast}
\left( \frac{x^2}{2 d^\ast}+ o(x^{1+\varepsilon})\right)=$$
\begin{equation} \label{eq:58}
=\frac{x^2}{2} \sum_{d \le x}
\frac{\mu_k(d)}{(d^\ast)^2}+o\left(x^{1+\varepsilon} \sum_{d \le x}
\frac{\mu_k(d)}{d^\ast}\right).
\end{equation}
Notice that since
$$d^\ast=\prod_{i=1}^{r} \frac{q_i^{k+1}-1}{q_i^k-1} > \prod_{i=1}^r
q_i=d,$$ we have
$$\left|\sum_{d \le x} \frac{\mu_k(d)}{d^\ast} \right|\le \sum_{d
\le x} \frac{1}{d}=O(\log x).$$ Moreover,
$$\left|\sum_{d \ge x} \frac{\mu_k(d)}{(d^\ast)^2} \right| \le
\sum_{ d>x} \frac{1}{d^2} \le \frac{1}{x-1}.$$ Therefore, by
(\ref{eq:58}),
$$\sum_{n \le x} \varphi_k(n)=\frac{x^2}{2} \sum_{i=1}^\infty
\frac{\mu_k(i)}{(i^\ast)^2}+o(x^{1+\varepsilon}),$$ where by
(\ref{eq:56}) $n^\ast$ is a $k$-multiplicative function.

Finally, using (\ref{eq:13}) for $\theta(n)=(n^\ast)^{-2}$ we obtain
the claim. \qed

In particular, when $k=1$, a result from \cite{cohe93} follows from
the theorem:
$$\sum_{n \le x} \varphi_1(n)=\frac{x^2}{2} \prod_{q \in Q^{(1)}}
\left(1-\frac{1}{(q+1)^2}
\right)+o(x^{1+\varepsilon})=0.3666252769\dots 
x^2+o(x^{1+\varepsilon}).$$ Here (and in what follows) the constant
was computed in \cite{finc04}, see also \cite{cohe,more00} for
efficient computational methods.


When $k \rightarrow \infty$ we find from the theorem that
\begin{equation} \label{eq:59}
\sum_{n \le x} \varphi(n) \sim \frac{x^2}{2} \prod_{p \in {\bf P}}
\left( 1-\frac{1}{p^2} \right)=\frac{3}{\pi^2} x^2.
\end{equation}

\section{Other Functions} \label{sec:other}

Let us consider several natural arithmetical functions.

\noindent {\bf 1.} The function $\tilde{\varphi_k}(n)$ has been
defined above in (\ref{eq:36}) and (\ref{eq:36a}) as a second
(formal) generalization of the Euler totient function. For $k=1$,
$\tilde{\varphi}_1(n)$ was considered in \cite{cohe93} and
\cite{finc04}. For it we analogously deduce:
$$\sum_{n \le x} \tilde{\varphi}_k(n)=\sum_{n \le x} \sum_{d{| \atop
k}n} \mu_k(d) \frac{n}{d}=\sum_{n \le x} n \sum_{d{| \atop k}n}
\frac{\mu_k(d)}{d}=$$
$$=\sum_{d \le x} \frac{\mu_k(d)}{d} \sum_{n \le x:\, d{| \atop
k}n} n=\sum_{d \le x} \frac{\mu_k(d)}{d} \nu_k(x,d)=$$
$$=\sum_{d \le x} \frac{\mu_k(d)}{d} \left(\frac{x^2}{2d^\ast}+o(x^{1+\varepsilon})
 \right)=\frac{x^2}{2} \sum_{i=1}^\infty \frac{\mu_k(i)}{i
 i^\ast}+o(x^{1+\varepsilon})=$$
 $$=\frac{x^2}{2} \prod_{q \in Q^{(k)}} \left(1-\frac{q^k-1}{(q^{k+1}-1)q}
 \right)+o(x^{1+\varepsilon}).$$
 In particular, when $k=1$,
 $$\sum_{n \le x} \varphi_1(n) \sim \frac{x^2}{2} \prod_{q \in
 Q^{(1)}} \left(1-\frac{1}{q(q+1)} \right)=0.3289358388\dots  x^2,$$
like in \cite{cohe93}, the constant has been computed in
\cite{finc04}. If $k \rightarrow \infty$ we arrive again at the
classical expression (\ref{eq:59}).

\noindent {\bf 2.} The summatory function for sums of $k$-divisors.

Consider $\sum_{n \le x} \sigma_k(n)$ where $\sigma_k(n)$ is the sum
of $k$-divisors of $n$. Analogously to Lemma \ref{lem:2} we obtain
from (\ref{eq:25}) the following result for the function
$\nu_k(x,d)$ from (\ref{eq:53}):
\begin{equation} \label{eq:62}
\nu_k(x,d)=\frac{x^2}{2 d^\ast}+o(x^{1+\varepsilon}),
\end{equation}
where
\begin{equation} \label{eq:63}
d^\ast=\prod_{q{| \atop k}d} \frac{q^{k+1}-1}{q^{k+1-d_q^{(k)}}-1},
\end{equation}
and $d_q^{(k)}$ is defined by the factorization (\ref{eq:5}) for
$n=d$. Furthermore,
$$\sum_{n \le x} \sigma_k(n)=\sum_{n \le x} \sum_{d{| \atop
k}n} \frac{n}{d}=\sum_{n \le x} n \sum_{d{| \atop k}n}
\frac{1}{d}=$$
$$=\sum_{d \le x} \frac{1}{d} \sum_{n \le x: \,d{| \atop
k}n} n=\sum_{d \le x} \frac{\nu_k(x,d)}{d}=$$
$$=\sum_{d \le x} \frac{1}{d} \left(\frac{x^2}{2
d^\ast}+o(x^{1+\varepsilon}) \right)=\frac{x^2}{2} \sum_{i=1}^\infty
\frac{1}{i i^\ast}+o(x^{1+\varepsilon}).$$ Setting in (\ref{eq:12}),
$\theta(n)=\frac{1}{n n^\ast}$ and noticing that by (\ref{eq:63}),
$$\theta(q^j)=\frac{q^{k-j+1}-1}{(q^{k+1}-1) q^j}, \quad
j=1,2,\dots ,k,$$ we find
$$\sum_{n \le x} \sigma_k(n)=\frac{x^2}{2} \prod_{q \in Q^{(k)}}
\left(1+\frac{q^{k+1}}{q^{k+1}-1} \sum_{j=1}^k
\frac{1}{q^{2j}}-\frac{1}{q^{k+1}-1} \sum_{j=1}^k \frac{1}{q^j}
\right)+o(x^{1+\varepsilon})=$$
$$=\frac{x^2}{2} \prod_{q \in Q^{(k)}} \left(1+\frac{q^k-1}{q^k(q^2-1)} \right)
+o(x^{1+\varepsilon}).$$ In particular, when $k=1$,
$$\sum_{n \le x} \sigma_1(n) \sim \frac{x^2}{2} \prod_{q \in
Q^{(1)}} \left(1+\frac{1}{q(q+1)} \right)=0.7307182421\dots  x^2,$$
coinciding with \cite{cohe93,finc04}. When $k \rightarrow \infty$ we
obtain a result from \cite{finc04},
$$\sum_{n \le x} \sigma(n) \sim \frac{x^2}{2} \prod_{p \in {\bf P}} \left(
1+\frac{1}{p^2-1} \right)=\frac{\zeta(2)}{2} x^2=\frac{\pi^2}{12}
x^2.$$

\noindent {\bf 3.} The numbers $k$-free from the $(i+1)$-st powers.

Consider the sequence $S_k(i)$ of numbers in $k$-arithmetics for
which in the canonical representation (\ref{eq:5}) only the powers
not exceeding $i$ are allowed, $i \le k-1$. Let us find the
asymptotics for the sum, $\sum_{n \in S_k^{(i)}} 1$. Using
inclusion-exclusion we have
$$\sum_{n \in S_k^{(i)}} 1=\lfloor x \rfloor - \sum_{q \le x}
\left\lfloor \frac{x}{q^{i+1}} \right\rfloor^{(k)}+\sum_{q_1<q_2 \le
x} \left\lfloor \frac{x}{q_1^{i+1} q_2^{i+1}}
\right\rfloor^{(k)}-\dots =$$
$$=\sum_{n \le x} \sum_{d^{i+1}{| \atop k}n} \mu_k(d)=\sum_{d \le
x^{\frac{1}{i+1}}} \mu_k(d) \sum_{n \le x:\, {d^{i+1}{| \atop
k}n}}1=$$
$$=\sum_{d \le x^{\frac{1}{{i+1}}}}  \mu_k(d) \left\lfloor
\frac{x}{d^{i+1}} \right\rfloor^{(k)}=\sum_{d \le
x^{\frac{1}{{i+1}}}} \mu_k(d) \left(\frac{x}{(d^{i+1})^\ast}
+o(x^\varepsilon) \right),$$ where the last equality is by Theorem
\ref{thm:2}. Therefore,
$$\sum_{n \in S_k^{(i)}} 1=x \sum_{d \le x^{\frac{1}{i+1}}}
\frac{\mu_k(d)}{(d^{i+1})^\ast}+o \left(
x^{\frac{1}{i+1}+\varepsilon}\right)=x \sum_{d=1}^\infty
\frac{\mu_k(d)}{(d^{i+1})^\ast}+o \left(
x^{\frac{1}{i+1}+\varepsilon}\right).$$ Since
$\frac{1}{(n^{i+1})^\ast}$ is a $k$-multiplicative function for a
fixed $i$, by (\ref{eq:13}) we conclude that
$$\sum_{n \in S_k^{(i)}} 1=x \prod_{q \in Q^{(k)}} \left(1-\frac{q^{k-i}-1}{q^{k+1}-i}
\right)+o \left( x^{\frac{1}{i+1}+\varepsilon}\right).$$ In
particular, when $k \rightarrow \infty$ we obtain the known result,
cf. \cite{sury70},
$$\sum_{n \in S_\infty^{(i)}} 1 \sim x \prod_{p \in P} \left(
1-\frac{1}{p^{i+1}} \right)=\frac{x}{\zeta(i+1)}.$$

\noindent {\bf 4.} $k$-complete numbers.

A number $n$ is called $k$-complete if in its factorization
(\ref{eq:5}) at least one $k$-prime has power $k$. Let $F_k(x)$ be
the number of $k$-complete numbers not exceeding $x$. For $k=1$
clearly $F_1(x)=\lfloor x \rfloor -1$. Using inclusion-exclusion,
for $k \ge 2$, we deduce
$$F_k(x)=
%\sum_{q \le x^{\frac1k}} \left\lfloor \frac{x}{q^k}
%\right\rfloor^{(k)}-\sum_{q_1<q_2 \le x^{\frac1k}} \left\lfloor
%\frac{x}{q_1^{k} q_2^k} \right\rfloor^{(k)}+\dots =$$
%$$=
-\sum_{n \le x^{\frac1k}} \sum_{d>1:\,d^{k}{| \atop
k}n} \mu_k(d)=\left\lfloor x^{\frac1k}\right\rfloor -\sum_{n \le
x^{\frac1k}} \sum_{d \ge 1:\,d^{k}{| \atop k}n} \mu_k(d)=$$
$$=\left\lfloor x^{\frac1k}\right\rfloor -\sum_{1 \le d \le
x^{\frac1k}} \mu_k(d) \sum_{n \le x^\frac1k:\,d^{k}{| \atop k}n}1=$$
$$=\left\lfloor x^{\frac1k}\right\rfloor -\sum_{1 \le d \le
x^{\frac1k}} \mu_k(d)  \left\lfloor \frac{x^\frac1k}{d^k}
\right\rfloor^{(k)}=$$
$$=\left\lfloor x^{\frac1k}\right\rfloor -\sum_{1 \le d \le
x^{\frac1k}} \left( \mu_k(d)
\frac{x^\frac1k}{(d^k)^\ast}+o(x^\varepsilon) \right),$$ where the
last equality is due to Theorem \ref{thm:2}. Furthermore,
$$F_k(x)=\left\lfloor x^{\frac1k}\right\rfloor-x^\frac1k \sum_{1 \le d \le
x^{\frac1k}} \frac{\mu_k(d)}{(d^k)^\ast}+o(x^{\frac1k+\varepsilon})=
$$
$$=x^\frac1k \left(1-\sum_{d=1}^\infty \frac{\mu_k(d)}{(d^k)^\ast}
\right)+o(x^{\frac1k+\varepsilon}).$$ Since $(n^k)^\ast$ is
$k$-multiplicative, then by (\ref{eq:13}) for $\theta(n)=(n^k)^\ast$
we have finally for $k \ge 2$,
$$F_k(x)= x^\frac1k \left(1-\prod_{q \in Q^{(k)}} \left(1-\frac{q-1}{q^{k+1}-1}
\right) \right)+o(x^{\frac1k+\varepsilon}).$$


\section{Relations Between $\varphi_k(n)$ and $\varphi(n)$}
\label{sec:relations}

Since for all $n$ and $k$ we have $\varphi_k(n) \ge \varphi(n)$, it
is of interest to study the equation
\begin{equation} \label{eq:64}
\varphi_k(n)-\varphi(n)=c,
\end{equation}
for a nonnegative constant $c$.

\begin{theorem} \label{thm:7}
For any nonnegative integer $c$ the equation (\ref{eq:64}) has an
infinite number of solutions.
\end{theorem}

\proof 1) Let $c=0$. Assume $n=p^a$, where $p$ is a prime, $a \ge
1$. Let $(k+1)^{m-1} \le a \le (k+1)^m$, and $a$ has the following
representation in the basis $k+1$:
$$a=(\alpha_{m-1}, \alpha_{m-2},\dots ,\alpha_0)_{k+1}, \quad 0 \le
\alpha_i \le k, \quad \alpha_{m-1} \ge 1.$$ Let us demonstrate that
$\varphi_k(p^a)=\varphi(p^a)$ if and only if all $\alpha_i \ge 1$,
$i=0,1,\dots ,m-2$. Indeed, let there exist $j \le m-2$ such that
$\alpha_j=0$. Then $p^{(k+1)^j} \le p^{(k+1)^{m-2}}<p^a,$ but
$\left( p^{(k+1)^j} , p^a\right)_k=1$. Therefore,
$\varphi_k(p^a)>\varphi(p^a)$, and we are done. In the opposite
direction, if $\varphi_k(p^a)>\varphi(p^a)$, then there exists $j
\le m-2$, for which $\left( p^{(k+1)^j} , p^a\right)_k=1$, but then
$\alpha_j=0$. In particular, if
$\alpha_0=\alpha_1=\dots =\alpha_{m-1}=1$ then, by the above claim, for
the number $a=1+(k+1)+(k+1)^2+\dots +(k+1)^{m-1}=\frac{(k+1)^m-1}{k}$
we have
$$\varphi_k \left(p^{\frac{1}{k} ((k+1)^m-1)} \right)=\varphi
 \left(p^{\frac{1}{k} ((k+1)^m-1)} \right)$$
 for every prime $p$ and integer $m$.

\noindent
 2) Let now $c \ge 1$. It is well known, see e.g. \cite{prac78},
 that for any $\varepsilon>0$ there exists $x_0(\varepsilon)$ such
 that for every $x>x_0(\varepsilon)$ between $x$ and
 $(1+\varepsilon) x$ there is a prime. Set
 $\varepsilon=\frac{1}{c}$. Choose a prime $p > \max \left( \frac{x_0\left(
 \frac1c\right)}{c},c \right)$, and set $x=cp$. Then $x>x_0 \left(
 \frac1c \right)$. Therefore, between $cp$ and
 $\left(1+\frac1c\right)cp=(c+1)p$, there is a prime. Let us denote
 it by $q$: $cp < q < (c+1)p$. We will show now that
 \begin{equation} \label{eq:65}
\varphi_k (p^k q)=\varphi(p^kq)+c.
 \end{equation}
Indeed, since $c<p$, the numbers
$$p^{k+1}, 2 p^{k+1},\dots , c p^{k+1},$$
are mutually $k$-prime with $p^{k}q$. Moreover $cp^{k+1}< p^k q$,
but $(c+1)p^{k+1}>p^kq$. This implies (\ref{eq:65}). The theorem is
proved since for every $c$ there exists an infinite set of
possibilities for the choice of relevant $p$ and $q$. \qed

Let us prove another statement about the intermediate position of
$\varphi_k(n)$ between $\varphi(n)$ and $n$.

\begin{theorem} \label{thm:8}
$$\liminf_{n \rightarrow \infty} \frac{\varphi_k(n)}{n}=0,
\quad \limsup_{n \rightarrow \infty}
\frac{\varphi_k(n)}{\varphi(n)}=\infty.$$
\end{theorem}

\proof Set $n=n_m=\prod_{i=1}^m p_i, m \ge 1,$ where $p_n$ is the
$n$-th prime. By Theorem \ref{thm:5}
\begin{equation} \label{eq:66}
\frac{\varphi_k(n_m)}{n_m}=\prod_{i=1}^m
\left(1+\frac{1}{p_i}+\dots +\frac{1}{p_i^k} \right)^{-1}+o\left(
n_m^{-1+\varepsilon} \right).
\end{equation}
We have
$$\prod_{i=1}^m
\left(1+\frac{1}{p_i}+\dots +\frac{1}{p_i^k} \right) \ge \prod_{i=1}^m
\left( 1+\frac{1}{p_i} \right)=$$
$$=\frac{\prod_{i=1}^m \left(1-\frac{1}{p_i^2} \right)}{\prod_{i=1}^m
\left(1-\frac{1}{p_i} \right)}=\frac{e^\gamma}{\zeta(2)} \ln p_m,$$
where for the last equality see \cite{prac78}, and $\gamma$ is the
Euler constant. Thus (\ref{eq:66}) yields the first statement of the
theorem.

Furthermore, for $n=n_m^{k+1}$ we deduce
\begin{equation} \label{eq:67}
\frac{\varphi_k(n_m^{k+1})}{\varphi(n_m^{k+1})}=\frac{\prod_{i=1}^m
\left(1+\frac{1}{p_i^{k+1}}+\dots +\frac{1}{p_i^{k(k+1)}}
\right)^{-1}+o\left( n_m^{(k+1)(-1+\varepsilon)}
\right)}{\prod_{i=1}^m \left(1-\frac{1}{p_i} \right)}.
\end{equation}
Since
$$\frac{\prod_{i=1}^m
\left(1+\frac{1}{p_i^{k+1}}+\dots +\frac{1}{p_i^{k(k+1)}}
\right)^{-1}}{\prod_{i=1}^m \left(1-\frac{1}{p_i}
\right)}>\frac{\prod_{i=1}^m \left(1-\frac{1}{p_i^{k+1}}
\right)}{\prod_{i=1}^m \left(1-\frac{1}{p_i}
\right)}=\frac{e^\gamma}{\zeta(k+1)} \ln p_m,$$ (\ref{eq:67}) yields
the second statement of the theorem. \qed

Furthermore, let us show that the following result is valid.

\begin{theorem} \label{thm:9new} For any natural number $k$,
\begin{equation}
\liminf_{n \rightarrow \infty} \frac{\varphi_k(n) \ln \ln
n}{n}=e^{-\gamma},
\end{equation}
where $\gamma$ is the Euler constant.
\end{theorem}

\proof The statement of the theorem is well known in the
conventional case $k=\infty$. Since for every natural $k$ we have
$\varphi_k(n) \ge \varphi(n)$, we conclude
$$\liminf_{n \rightarrow \infty} \frac{\varphi_k(n) \ln \ln
n}{n} \ge e^{-\gamma}.$$ Thus, to prove the theorem it is sufficient
to present a sequence $\{n_m\}$ on which the equality holds. We will
demonstrate that the sequence
\begin{equation} \label{eq:beta}
n_m=\prod_{q \in Q^{(k)}, q \le \ln m} q
\end{equation}
satisfies the requirement. Notice that for $k$-primes we have
\begin{equation} \label{eq:gamma}
\prod_{q \in Q^{(k)}, q \le n} q \sim e^{n+o(n)}.
\end{equation}
Consequently for the sequence (\ref{eq:beta}) we have
\begin{equation} \label{eq:delta}
n_m \sim e^{\ln m+o(\ln m)}=m^{1+o(1)}.
\end{equation}
Using (\ref{eq:delta}) and Theorem \ref{thm:5} we find
$$\frac{\varphi_k(n_m) \ln \ln
n_m}{n_m}=(\ln \ln n_m) \prod_{q \le \ln m}
\left(1+\frac{1}{q}+\ldots+\frac{1}{q_k}
\right)^{-1}+O(n_m^{-1+\varepsilon})=$$
$$=(\ln \ln n_m) \prod_{q \le \ln m} \left( \left(1-\frac{1}{q^{k+1}} \right)^{-1}
\left(1-\frac{1}{q} \right)\right)+O(n_m^{-1+\varepsilon})=$$
$$=(\ln \ln n_m) \prod_{q \le \ln m}  \left(1-\frac{1}{q^{k+1}} \right)^{-1}
\prod_{p \le \ln m} \left(1-\frac{1}{p} \right) \cdot
$$ $$\cdot \left(\frac{\prod_{q \le \ln m} \left(1-\frac{1}{q}
\right)}{\prod_{p \le \ln m} \left(1-\frac{1}{p} \right)}
\right)+O(n_m^{-1+\varepsilon}).$$ However, from the definition of
the set $Q^{(k)}$ we have that
\begin{equation} \label{eq:kappa}
\frac{\prod_{q \le \ln m} \left(1-\frac{1}{q} \right)}{\prod_{p \le
\ln m} \left(1-\frac{1}{p} \right)}=\prod_{q \le (\ln
m)^{\frac{1}{k+1}}} \left(1-\frac{1}{q^{k+1}} \right).\end{equation}
Thus,
%$$\frac{\varphi_k(n_m) \ln \ln n_m}{n_m}=$$
\small
\begin{equation} \label{eq:lambda}
\frac{\varphi_k(n_m) \ln \ln n_m}{n_m}
=(\ln \ln n_m) \!\!\!\!\!\prod_{(\ln m)^{\frac{1}{k+1}}\le q \le \ln m}
\left(1-\frac{1}{q^{k+1}} \right)^{-1} \prod_{p \le \ln m}
\left(1-\frac{1}{p} \right)+O(n_m^{-1+\varepsilon}).
\end{equation}
\normalsize
It is well known (see e.g. \cite{prac78}) that
\begin{equation} \label{eq:mu}
\prod_{p \le x} \left(1-\frac{1}{p} \right)=\frac{e^{-\gamma}}{\ln
x} \left( 1+O\left( e^{-c \sqrt{\ln x}} \right) \right),
\end{equation}
where $c$ is a positive constant.

Let us also estimate $$\prod_{(\ln m)^{\frac{1}{k+1}}\le q \le \ln
m} \left(1-\frac{1}{q^{k+1}} \right)^{-1}.$$ Since for $0 < x < 1$
we have
$$-\ln (1-x)=\int_0^x \frac{dt}{1-t} \le \frac{x}{1-x},$$
for $m$ large enough  we deduce
$$\ln \prod_{(\ln m)^{\frac{1}{k+1}}\le q \le \ln m}
\left(1-\frac{1}{q^{k+1}} \right)^{-1} \le \sum_{(\ln
m)^{\frac{1}{k+1}}\le q \le \ln m} \frac{1}{(q-1)^{k+1}} \le$$
$$\le \int_{(\ln m)^{\frac{1}{k+1}}-1}^{\ln m-1} \frac{dt}{t^{k+1}}=O \left( (\ln
m)^{-\frac{k}{k+1}}\right).$$ Therefore,
\begin{equation} \label{eq:nu}
\prod_{(\ln m)^{\frac{1}{k+1}}\le q \le \ln m}
\left(1-\frac{1}{q^{k+1}} \right)^{-1}=1+O \left( (\ln
m)^{-\frac{k}{k+1}}\right).
\end{equation}
Taking into account that from (\ref{eq:delta}) it follows that
$$\frac{\ln \ln n_m}{\ln \ln m}=1+o\left(\frac{1}{\ln \ln m}
\right),$$ we deduce from (\ref{eq:lambda}), (\ref{eq:mu}) for
$x=\ln m$, and (\ref{eq:nu}) that
$$\frac{\varphi_k(n_m) \ln \ln n_m}{n_m}=e^{-\gamma} \left(1+O \left(
\frac{1}{\ln \ln m}\right) \right).$$
 \qed

Let us also mention that  since
$$e^{c \sqrt{\ln x}}=o\left(x^{\frac{k}{k+1}} \right),$$
i.e.,
$x^{-\frac{k}{k+1}}=o(e^{-c \sqrt{\ln x}}),$
it follows from (\ref{eq:kappa}), (\ref{eq:mu}) and (\ref{eq:nu})
that the following equality, being a $k$-generalization of
(\ref{eq:mu}), holds:
\begin{equation} \label{eq:tau}
\prod_{q \le x} \left(1-\frac{1}{q} \right)=\frac{e^{-\gamma}}{\ln
x} \left( \prod_{q \in Q^{(k)}} \left( 1-\frac{1}{q^{k+1}}
\right)\right) \left(1+O(e^{-c \sqrt{x}}) \right).
\end{equation}
Applying $\ln$ to (\ref{eq:tau}), after simple transformations we
find
\small
$$\sum_{q \le x} \frac{1}{q}=\ln \ln x+\gamma-\sum_{q \in Q^{(k)}}
\sum_{j \ge 2} \frac{1}{j q^j}%+$$
%$$
+\sum_{q \in Q^{(k)}} \sum_{j \ge 1} \frac{1}{j
q^{(k+1)j}}+O(e^{-c \sqrt{\ln x}})%=$$
%$$
=\ln \ln x+B_k+O(e^{-c \sqrt{\ln x}}),$$
\normalsize
where
$$B_k=\gamma+\sum_{q \in Q^{(k)}} \frac{1}{q^{k+1}}-\sum_{q \in
Q^{(k)}} \sum_{j \ge 2}  \frac{1}{j q^j} \left(1-\frac{1}{q^{kj}}
\right).$$ The latter for $k=\infty$ becomes
$$B=\gamma-\sum_p \sum_{j \ge 2} \frac{1}{j p^j}=0.2614972128\dots $$
and is known as the prime reciprocal constant, the Mertens constant,
the Kronecker constant, or the Hadamard-de La Vall\'{e}e-Poussin
constant.


\section{Analogs of the Wirsing and Delange Theorems} \label{sec:wirsing}

Since the $k$-multiplicative functions are multiplicative as well in
the conventional sense, all the theorems about multiplicative
functions are formally valid for $k$-multiplicative functions.
However, it is worth noticing that from the point of view of the
standard arithmetics the $k$-multiplicative functions are
"under-defined" since they are defined only on a small subset of the
set of prime numbers. For example, when $k=2$ this subset is $\{p,
p^2, p^3, p^6, p^9, p^{18},\dots \}$ and the direct application of
known asymptotic theorems about multiplicative functions seems to be
impossible. Therefore, the question about $k$-analogs of such
theorems is non-trivial. For this goal we have chosen the well known
theorems of Wirzing and Delange. Note that the condition on
$k$-multiplicativity allows an essential simplification of the
statements of these theorems.

\begin{theorem} a) (Wirzing, see \cite{post88}) Let $h(n)$ be a
multiplicative function satisfying

1) $h(n) \ge 0$, $n=1,2,\dots $;

2) $h(p^\nu)\le c_1 c_2^\nu$, \ $p \in {\bf P}$, \ $\nu=1,2,\dots ,
c_2<2$;

3) $\sum_{p \le x, p \in {\bf P}} h(p)=(\tau+o(1)) \frac{x}{\ln x},$
where $\tau \ge 0,$ is a constant.

\noindent
Then, for $x \rightarrow \infty$,
\begin{equation} \label{eq:68}
\sum_{n \le x} h(n)=\left(\frac{e^{-\gamma \tau}}{\Gamma(\tau)}+o(1)
\right) \frac{x}{\ln x} \prod_{p \le x, p \in {\bf P}}
\left(1+\frac{h(p)}{p}+\frac{h(p^2)}{p^2}\dots  \right)
\end{equation}
where $\Gamma(x)$ is the gamma-function, and $\gamma$ is the Euler
constant.

\bigskip

\noindent b) ($k$-analog) Let $h(n)$ be a $k$-multiplicative
function satisfying

1) $h(n) \ge 0$, $n=1,2,\dots $;

2) $h(q^r) \le c, q \in Q^{(k)}, r=1,2,\dots ,k;$

3) $\sum_{q \le x, q \in Q^{(k)}} h(q)=(\tau+o(1)) \frac{x}{\ln x},$
where $\tau \ge 0,$ is a constant.

\noindent
Then,
\begin{equation} \label{eq:69}
\sum_{n \le x} h(n)=\left(\frac{e^{-\gamma \tau}}{\Gamma(\tau)}+o(1)
\right) \frac{x}{\ln x} \prod_{q \le x, q \in Q^{(k)}}
\left(1+\frac{h(q)}{q}+\dots +\frac{h(q^k)}{q^k}\right).
\end{equation}
\end{theorem}

\begin{theorem} \label{thm:10}
a) (Delange, see \cite{post88}) Let $h(n)$ be a multiplicative
function such that

1) $|h(n)|\le 1, n=1,2,\dots ;$

2) the series $\sum_{p \in {\bf P}} \frac{1-h(p)}{p}$ converges.

\noindent
Then,
\begin{equation} \label{eq:70}
\lim_{n \rightarrow \infty} \frac{1}{n} \sum_{m=1}^n h(m)=\prod_{p
\in {\bf P}} \left(1-\frac{1}{p} \right) \left(1+\sum_{j=1}^\infty
\frac{h(p^j)}{p^j} \right).
\end{equation}

\bigskip

\noindent b) ($k$-analog) Let $h(n)$ be a $k$-multiplicative
function satisfying

1) $|h(n)| \le 1$, $n=1,2,\dots ;$

2) the series $\sum_{q \in Q^{(k)}} \frac{1-h(q)}{q}$ converges.

\noindent
Then,
\begin{equation} \label{eq:71}
\lim_{n \rightarrow \infty} \frac{1}{n} \sum_{m=1}^n h(m)=\prod_{q
\in Q^{(k)}} \frac{q-1}{q^{k+1}-1} \sum_{i=0}^k q^{k-i} h(q^i).
\end{equation}
\end{theorem}

\proof We just prove the $k$-analog of the Delange theorem, the
proof the previous theorem is similar. Notice that under the
conditions of b) of Theorem \ref{thm:10}, the conditions of a) are
also valid. We have
\begin{eqnarray}\label{eq:72}
1-\frac1p&=&\frac{1-\frac1p}{1-\frac{1}{p^{k+1}}} \cdot
\frac{1-\frac{1}{p^{k+1}}}{1-\frac{1}{p^{(k+1)^2}}} \cdot
\frac{1-\frac{1}{p^{(k+1)^2}}}{1-\frac{1}{p^{(k+1)^3}}} \dots \nonumber\\
%=$$ 
&=&\prod_{\ell=0}^\infty \left(1+\frac{1}{p^{(k+1)^\ell}}+
\frac{1}{p^{2(k+1)^\ell}}+\dots +\frac{1}{p^{k(k+1)^\ell}}
\right)^{-1}\nonumber\\%=$$
%\begin{equation} 
&=&\prod_{q \in Q^{(k)}:\,p|q}
\left(1+\frac1q+\frac{1}{q^2}+\dots +\frac{1}{q^k} \right)^{-1}.
\end{eqnarray}
Further, using the $k$-multiplicativity of $h(n)$ for a fixed $p \in
{\bf P}$ we have
\begin{eqnarray*}
1+\sum_{j=1}^\infty \frac{h(p^j)}{p^j}= \prod_{q \in Q^{(k)}:\,p|q}
\left(1+\frac{h(q)}{q}+\dots +\frac{h(q^k)}{q^k} \right),
\end{eqnarray*}
and consequently
\begin{equation}
\label{eq:73} \prod_{p \in {\bf P}} \left( 1+\sum_{j=1}^\infty
\frac{h(p^j)}{p^j}\right)=\prod_{q \in Q^{(k)}}
\left(1+\frac{h(q)}{q}+\dots +\frac{h(q^k)}{q^k} \right).
\end{equation}
Substituting (\ref{eq:72}) and (\ref{eq:73}) into (\ref{eq:70}) we
find:
$$\lim_{n \rightarrow \infty} \frac1n \sum_{m=1}^n h(m)= \prod_{q \in
Q^{(k)}} \left(1+\frac1q+\frac1{q^2}+\dots +\frac{1}{q^k} \right)^{-1}
\left(1+\frac{h(q)}{q}+\frac{h(q^2)}{q^2}+\dots +\frac{h(q^k)}{q^k}
\right),$$ and (\ref{eq:71}) follows. \qed

\section{Perfect Numbers} \label{sec:perfect}

A number $n$ is called $k$-perfect if it equals to the sum of its
proper positive $k$-divisors. It follows from (\ref{eq:5}) that any
$k$-perfect number satisfies
\begin{equation} \label{eq:74}
\sigma_k(n)=\prod_{q {| \atop k} n} \frac{q^{n_q+1}-1}{q-1}=2n,
\end{equation}
where $\sigma_k(n)$ is the sum of $k$-divisors of $n$. For example,
$28$ is $k$-perfect for all $k \ge 2$.

Consider a sequence $S=\{n_k\}_{k \in T},$ such that $n_k$ is a
$k$-perfect number of the form
\begin{equation} \label{eq:75}
n_k=2^{k+1} (2 l-1),
\end{equation}
where $(2l-1)$ possesses the conventional factorization (\ref{eq:1})
into primes having powers not exceeding $k$, and $T$ is the set of
such $k$ for which there exists at least one $k$-perfect number of
the form (\ref{eq:75}). We will address such numbers as being of
type $S$. Hence by (\ref{eq:74}) for $n_k$ we have
$$\sigma_k(n_k)=(2^{k+1}+1) \prod_{p|2l-1}
\frac{p^{n_p+1}-1}{p-1}=2^{k+2}(2l-1).$$

\begin{example} \label{ex:7} {\rm
In the following table we present examples of $k$-perfect numbers of
type $S$ for every $k$, $1 \le k \le 10$.
$$
\begin{array}{|r|c|}
\hline k & n \\
\hline 1& 2^2\cdot 3 \cdot 5 \\
\hline 2 & 2^3 \cdot 3^2 \cdot 7 \cdot 13 \\
\hline 3 & 2^4 \cdot 3^2 \cdot 7 \cdot 13 \cdot 17 \\
\hline 4 & 2^5 \cdot 3^2 \cdot 7 \cdot 11 \cdot 13 \\
\hline 5 & 2^6 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \\
\hline 6 & 2^7 \cdot 3^2 \cdot 7 \cdot 11 \cdot 13 \cdot 43 \\
\hline 7 & 2^8 \cdot 3^2 \cdot 7 \cdot 11 \cdot 13 \cdot 43 \cdot
257 \\
\hline 8 & 2^9 \cdot 3^3 \cdot 5^2 \cdot 19 \cdot 31 \\
\hline 9 & 2^{10} \cdot 3 \cdot 5^2 \cdot 7 \cdot 31 \cdot 41 \\
\hline 10 & 2^{11} \cdot 3^3 \cdot 5^2 \cdot 19 \cdot 31 \cdot 683
\\
\hline
\end{array}
$$
} 
\end{example}

Notice that in the examples with the pairs of $k$-perfect numbers of
type $S$ for $k_1=2,$ $k_2=3$; $k_1=2,$ $k_2=4$; $k_1=4$, $k_2=6$;
$k_1=6$, $k_2=7$; $k_1=8$, $k_2=10$; the ratio of the $k$-perfect
numbers in these pairs are $2^{k_2-k_1} p$ where $p$ is a prime not
dividing the first number in the pair. The corresponding primes in
the examples are $17$, $11$, $43$, $257$, and $683$. This hints at a
general description of all such pairs of type $S$.

\begin{theorem} \label{thm:11}
Let $n_1$ be a $k$-perfect number of type $S$. For $n_2$ to be a
$(k+m)$-perfect number of type $S$ having the form
$$n_2=2^m n_1 p,$$
where $p$ is a prime, $p$ does not divide $n_1$, it is necessary and
sufficient that one of the following conditions is valid

\begin{enumerate}
\item $m=1$, $p$ is a Fermat prime of the form $2^{k+2}+1$;
\item $m=2$, $p$ is a prime of the form $\frac{2^{k+3}+1}{3}$ for an
even $k$.
\end{enumerate}
\end{theorem}

Theorem \ref{thm:11} claims that there are no considered pairs of
$k$-perfect numbers of type $S$ if $k_2-k_1 \ge 3$. Under validity
of the conjecture that there is a finite number of Fermat primes,
the number of considered pairs satisfying $k_2-k_1=1$ is also
finite. Finally, if $k_2-k_1=2$, notice that $\frac{2^{k+3}+1}{3}$
can be prime only if $k+3$ is prime. It is conjectured in
\cite{bate89} that the number of primes having form
$\frac{2^p+1}{3}$ is infinite and, moreover, the number of such
primes not exceeding $x$ is approximately $e^\gamma \log_2 x$,
$\gamma$ is the Euler constant.

For the proof of Theorem \ref{thm:11} we will need the following
result.

\begin{lemma} \label{lem:3}
The Diophantine equation
\begin{equation} \label{eq:76}
2^{k+m+1}+1=n(2^m-1),
\end{equation}
for $k \ge 1$, $m \ge 1$, $n \ge 1$, has only the following
solutions:
\begin{equation} \label{eq:77}
m=1, k \in \N, n=2^{k+2}+1,
\end{equation}
\begin{equation} \label{eq:78}
m=2, k=2r, r \in \N, n=\frac{2^{k+3}+1}{3}.
\end{equation}
\end{lemma}

\proof The case $m=1$ is trivial. Assume $m \ge 2$. Let
\begin{equation} \label{eq:79}
k=rm+s, \quad 0 \le s \le m-1.
\end{equation}
We have
$$(2^m-1) \sum_{i=0}^{\lfloor k/m \rfloor} 2^{k-mi} = 2^{k-rm}
(2^{m(r+1)}-1)=2^{k+m}-2^s.$$ Therefore,
$$2^{k+m} \equiv 2^s \mbox{\rm \, mod} (2^m-1),$$
and
$$2^{k+m+1}+1 \equiv 2^{s+1}+1 \mbox{\rm \, mod} (2^m-1).$$
Now, from (\ref{eq:76}) it follows that
\begin{equation} \label{eq:80}
2^{s+1}+1 \equiv 0 \mbox{\rm \, mod} (2^m-1).
\end{equation}
Since $2(2^m-1)>2^m+1 \ge 2^{s+1}+1$, (\ref{eq:80}) is possible only
if $2^{s+1}+1=2^m-1,$ or $2^{m-1}-2^s=1$. The last relation can be
valid only if $m=2$, $s=0$. Therefore, by (\ref{eq:79}), $k=2r$.
This gives (\ref{eq:78}). \qed

\noindent
{\it Proof of Theorem \ref{thm:11}}. Let $n_1$ be a $k$-perfect
number of type $S$, i.e.
\begin{equation} \label{eq:81}
n_1=2^{k+1} (2l-1),
\end{equation}
where the factorization (\ref{eq:1}) of $(2l-1)$ has powers of the
primes not exceeding $k$. This means that
$$\sigma_k(2l-1)=\sigma(2l-1).$$
By (\ref{eq:74}) specified for $n_1$ and by the $k$-multiplicativity
of $\sigma_k(n)$ we have
\begin{equation} \label{eq:82}
(2^{k+1}+1) \sigma(2l-1)=2^{k+2} (2l-1).
\end{equation}
Furthermore, by (\ref{eq:74}), the number
\begin{equation} \label{eq:83}
n_2=2^{k+m+1} (2l-1) p, p \not| n_1,
\end{equation}
is a $(k+m)$ -perfect number of type $S$ if and only if
\begin{equation} \label{eq:84}
\left(2^{k+m+1}+1 \right) \sigma(2l-1) (p+1)=2^{k+m+2} (2l-1) p.
\end{equation}
Dividing (\ref{eq:84}) by (\ref{eq:82}) we find
$$\frac{(2^{k+m+1}+1)(p+1)}{2^{k+1}+1}=2^m p,$$
yielding
$$p=\frac{2^{k+m+1}+1}{2^m-1}.$$
By Lemma \ref{lem:3} only two possibilities are relevant:

1) $m=1$, $p=2^{k+2}+1$.

Clearly, $k+2$ cannot have odd prime factors. Therefore,
$k+2=2^{\nu-1},$ $\nu \in \N$. Thus, $p=2^{2^{\nu-1}}+1$, i.e. is a
Fermat prime.

2) $m=2$, $p=\frac{2^{k+3}+1}{3}$.

In this case, $k+3$ is prime.

Let us demonstrate, in the opposite direction, that if $n_1$ from
(\ref{eq:81}) is $k$-perfect, then $n_2$ from (\ref{eq:83}) for
\begin{equation} \label{eq:85}
p=2^{k+2}+1
\end{equation}
is $(k+1)$-perfect, and for
\begin{equation} \label{eq:86}
p=\frac{2^{k+3}+1}{3}, \quad k \mbox{\rm \ even},
\end{equation}
is $(k+2)$-perfect.

Indeed, when (\ref{eq:85}) holds, multiplying (\ref{eq:82}) by
$2(2^{k+2}+1)=2p$, and noticing that $2(2^{k+1}+1)=p+1$, we find
$$(2^{k+2}+1)(p+1)\sigma(2l-1)=2^{k+3} (2l-1) p,$$
corresponding to (\ref{eq:84}) for $m=1$. Therefore, the number
$n_2$ is $(k+1)$-perfect for $m=1$.

Under (\ref{eq:86}), multiplying (\ref{eq:82}) by $4
\frac{2^{k+3}+1}{3}=4p,$ and noticing that $\frac{4}{3}
(2^{k+1}+1)=p+1$, we find
$$(2^{k+3}+1)(p+1) \sigma(2l-1)=2^{k+4} (2l-1) p,$$
corresponding to (\ref{eq:84}) for $m=2$. Therefore, $n_2$ is
$(k+2)$-perfect for $m=2$.
\qed

\begin{example} \label{ex:8} {\rm For $k=14$ the number $2^{16}+1$ is a Fermat
prime. It is easily checked using (\ref{eq:74}) that
\begin{equation} \label{eq:87}
2^{15} \cdot 3^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 83 \cdot
331
\end{equation}
is $14$-prime. Therefore using Theorem \ref{thm:11} with $m=1$ we
find the following $15$-perfect number
$$2^{16} \cdot 3^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 83
\cdot 331 \cdot 65537.$$

When $k=10$, the number $\frac{2^{13}+1}{3}=2731$, is prime. Using
Theorem \ref{thm:11} for $m=2$, we have, along with the last number
in the table of Example \ref{ex:7}, the following $12$-perfect
number:
\begin{equation} \label{eq:88}
2^{13} \cdot 3^3 \cdot 5^2 \cdot 19 \cdot 31 \cdot 683 \cdot 2731.
\end{equation}

Furthermore, using $14$-perfect number (\ref{eq:87}), and taking
into account that $\frac{2^{17}+1}{3}=43691$ is prime, we find
analogously the following $16$-perfect number:
$$2^{17} \cdot 3^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 83
\cdot 331 \cdot 43691,$$ which in turn yields, since
$\frac{2^{19}+1}{3}=174763$ is prime, the following $18$-perfect
number
$$2^{19} \cdot 3^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 83
\cdot 331 \cdot 43691 \cdot 174763.$$ }
\end{example}

\begin{example} \label{ex:9}
{\rm  Notice that for the same $k$ we may have different $k$-perfect
numbers of type $S$. For example, when $k=8$, along with the number
given in Example \ref{ex:7}, we have another $8$-perfect number
$$2^9 \cdot 3^4 \cdot 7 \cdot 11^2 \cdot 19^2 \cdot 127.$$
Therefore, by Theorem \ref{thm:11}, we find a $10$-perfect number
which differs from the corresponding number in Example \ref{ex:7},
$$2^{11} \cdot 3^4 \cdot 7 \cdot 11^2 \cdot 19^2 \cdot 127 \cdot
683,$$ which in turn yields yet another $12$-perfect number
different from (\ref{eq:88}),
$$2^{13} \cdot 3^4 \cdot 7 \cdot 11^2 \cdot 19^2 \cdot 127 \cdot 683
\cdot 2731.$$} \end{example}

\section{Mixed Multiplicative Factorizations} \label{sec:mix}

Consider an infinite sequence of positive integers ${\bf k}=(k_1,
k_2,\dots )$. Let us introduce the corresponding multiplicative basis
\begin{equation} \label{eq:89}
Q^{({\bf k})}=\left\{p_i^{(k_i+1)^{j-1}}\Big| p_i \mbox{\rm \ being
the $i$-th prime},  i, j \in \N \right\}.
\end{equation}
Analogously to (\ref{eq:5}) we find the unique factorization for
every $n \in \N$ in this basis:
\begin{equation} \label{eq:90}
n = \prod_{q \in Q^{({\bf k})}} q^{n_q^{({\bf k})}},
\end{equation}
where $n_q^{({\bf k})}\le k_i,$ if $q$ is divisible by $p_i$. Note
that some of $k_i$'s can be assumed to be $\infty$.

Analogously we introduce the notion of divisibility $m {| \atop {\bf
k}} n$, the greatest common divisor
$$(m,n)_{\bf k}=\max_{d {| \atop {\bf k}} m, d {| \atop {\bf k}} n}  d,$$
and all the above-defined functions. For example, the M\"{o}bius
function is defined as
$$\mu_{\bf k}(n)=\left\{\begin{array}{rl} (-1)^{\sum_{q {| \atop {\bf k}} n}
1}, & \mbox{\rm if all $n_q^{({\bf k})}=1$}\\
0, & \mbox{\rm otherwise.}
\end{array} \right.$$
Furthermore,
$$\left\lfloor \frac{x}{m}\right\rfloor^{({\bf k})}=\sum_{n \le x: m {| \atop {\bf k}}
n} 1,$$
$$\varphi_{\bf k}(x,n)=\sum_{1 \le j \le x: (j,n)_{\bf k}=1} 1,
\quad \varphi_{\bf k}(n)=\varphi_{\bf k}(n,n). $$ Notice that from
the proofs of Theorems \ref{thm:2} and \ref{thm:5} it follows that
the asymptotic formula (\ref{eq:48}) is uniform also in $k$. Let
$I_n$ be the set of indices of the primes dividing $n$.
%Setting
%$$\kappa_{\bf k} (n)=\prod_{i \in I_n} \prod_{q {| \atop k_i}
%n:\,p_i|q} \left(1+\frac{1}{q}+\dots +\frac{1}{q^{k_i}} \right)^{-1},$$
%\begin{equation} \label{eq:91}
%a_{\bf k}=\frac{1}{2} \prod_{i=1}^\infty \prod_{q \in Q^{({\bf
%k})}:\, p_i|q} \left(1-\left(\frac{q^{k_i}-1}{q^{k_i+1}-1} \right)^2
%\right),
%\end{equation}
We have the following generalizations of Theorems \ref{thm:5} and
\ref{thm:6}.

\begin{theorem} \label{thm:5'}
$$\varphi_{\bf k}(x,n)=\kappa_{\bf k}(n) x+O \left( (nx)^\varepsilon
\right),$$ where
$$\kappa_{\bf k} (n)=\prod_{i \in I_n} \prod_{q {| \atop k_i}
n:\,p_i|q} \left(1+\frac{1}{q}+\dots +\frac{1}{q^{k_i}} \right)^{-1}.$$
\end{theorem}

\begin{theorem} \label{thm:6'}
$$\sum_{n \le x} \varphi_{\bf k}(n)=a_{\bf k}
x^2+o\left(x^{1+\varepsilon}\right),$$ where
\begin{equation} \label{eq:91}
a_{\bf k}=\frac{1}{2} \prod_{i=1}^\infty \prod_{q \in Q^{({\bf
k})}:\, p_i|q} \left(1-\left(\frac{q^{k_i}-1}{q^{k_i+1}-1} \right)^2
\right).
\end{equation}
\end{theorem}

Note that we have continuum of mixed multiplicative bases.

\section{Open Problems} \label{sec:open}

\noindent 1. Find asymptotics for $\sum_{n \le x} d_k(n)$ where
$d_k(n)$ is the number of $k$-factors of $n$ (the Dirichlet
$k$-divisors problem). It is well known that for $k=\infty$ by the
classical result due to Dirichlet
\begin{equation} \label{eq:95}
\sum_{n \le x} d(n)=x \ln x+(2 \gamma-1)x+O \left(
x^{\frac12}\right),
\end{equation}
where $\gamma$ is the Euler constant. For better estimates of the
residual term see \cite{iwan04,redm96} and references therein. When
$k=1$ the only known estimate \cite{cohe93} is
$$\sum_{n \le x} d_1(n)=c_1 x \ln x+(2 \gamma_1-c_1)
x+o\left(x^{\frac12+\varepsilon}\right),$$ where
$$c_1=\prod_{q \in Q^{(1)}} \left(1-\frac{1}{(q+1)^2}
\right)=0.73325055\dots $$ and $\gamma_1$ is a constant. It would be
natural to conjecture that
$$\sum_{n \le x} d_k(n)=c_k x \ln x+(2 \gamma_k-c_k) x+o \left(
x^{\frac12+\varepsilon}\right),$$ so that
$$\lim_{k \rightarrow \infty} c_k=1, \quad \lim_{k \rightarrow \infty}
\gamma_k=\gamma.$$

\noindent 2. Find the sum of $k$-complete numbers not exceeding $x$
(see Section \ref{sec:other}).

\noindent 3. A number $n$ is called $k$-compact if in its
$k$-factorization (\ref{eq:5}) all $k$-primes are pairwise mutually
prime (in the conventional sense). In particular all natural numbers
are $\infty$-compact. The following are open problems: a) find the
number of $k$-compact numbers not exceeding $x$; b) find the sum of
$k$-compact numbers not exceeding $x$.

\noindent 4. a) Is the size of the union of the sets of $k$-perfect
number of type $S$, $k=1,2,\dots $ (see Section \ref{sec:perfect})
infinite? In other words, whether the table of Example \ref{ex:7}
has an infinite number of rows?

\noindent b) Is there a value $k$ for which the set of $k$-perfect
numbers of type $S$ is empty? We conjecture that there is. For
instance we do not know if there are $11$-perfect and/or
$13$-perfect numbers of type $S$.

\noindent 5. Estimate the least term of the sequence $\{n_k^{(c)}\}$
and the density of this sequence (see Theorem \ref{thm:7}).

\noindent 6. a) Do we have for every $k \in \N$ an infinite number
of $n$ such that $\varphi_k(n)=n \kappa_k(n)$ (see Theorem
\ref{thm:5} for $x=n$)? Notice that for $n \le 1000$ there are only
6 solutions to the equation $\varphi_1(n)=n \kappa_1(n)$
\cite{shev96}, namely, 1, 6, 60, 120, 360, 816.

\noindent b) For every $x \le 1000$, we have that the number of
those $n \le x$ for which $n \kappa_1(n) > \varphi_1(n)$ is greater
than the number of those not satisfying the inequality. For example,
when $x=1000$ the number of such $n$ is 565. Is that true for all
$x$?

\noindent 7. For every pair of mutually prime $m$ and $n$, find
$\min_{t \in \N} \left\lfloor \frac{nt}{mt}\right\rfloor$ (see
Section \ref{sec:function}).

\noindent 8. N.~P.~Romanov, see \cite{prac78}, proved that
$$\sum_{n=2}^\infty \frac{\varphi(n)}{n} x^n=\frac{6}{\pi^2}
\sum_{n=1}^\infty \frac{\mu(n)}{n^2} \prod_{p|n, p \in {\bf P}}
\left(1-\frac{1}{p^2} \right)^{-1} S_n(x),$$ where
$$S_n(x)=\sum_{\rho=\rho(n)} \frac{\rho^2 x^2}{1-\rho x},$$
with the summation over all primitive $n$-th roots of unity. Find a
$k$-analog of this identity for $\sum_{n=2}^\infty
\frac{\varphi_k(n)}{n} x^n$.

\noindent 9. Is the set of constants $a_{\bf k}$ (see (\ref{eq:91}))
everywhere dense in the interval $\left[ a_{{\bf k}_1}, a_{{\bf
k}_2}\right]$, where ${\bf k}_1=(\infty, \infty, \dots )$ and ${\bf
k}_2=(1,1,\dots )$, i.e., in the interval
$$\left[\frac{3}{\pi^2},\frac12 \prod_{q \in Q^{(1)}} \left(1-\frac{1}{(q+1)^2}
 \right) \right]=[0.303963551\dots ,0.3666252769\dots ]?$$

%\noindent 10. Having the factorization (\ref{eq:1}) of a number $n$,
%we call it even- or odd-factorizable depending on the parity of the
%sum of the exponents. In particular, $1$ is assumed to be
%even-factorizable. P\'{o}lya \cite{poly90} conjectured that for $n
%\ge 2$ the even-factorizable numbers never constitute majority.
%Analogously, the notion of even- and odd- factorizable numbers can
%be defined for $k$-factorization (\ref{eq:5}). In particular, $1$ is
%even-factorizable for every $k$. Let $k=1$. There is a numerical
%evidence that the P\'{o}lya conjecture is apparently wrong here
%starting from some $n_0$. For instance, the interval $[2,400]$ is
%partitioned to eight such sub-intervals that among the first $n$
%numbers there is the majority of those numbers with the parity of
%$1$-factorization coinciding with the number of the sub-interval. We
%conjecture that there is no $n_0$ such that among the first $n$
%numbers for all $n >n_0$, the numbers with a prescribed parity of
%$1$-factorization constitute the majority.

\section{Acknowledgement}

We are grateful to the anonymous referee for valuable comments.

\begin{thebibliography}{99} \footnotesize

\bibitem{andr76} G.~E.~Andrews, {\it Theory of Partitions},
Addison-Wesley, 1976.

\bibitem{bate89} P.~T.~Bateman, J.~L.~Selfridge, amd S.~S.~Wagstaff, The
new Mersenne conjecture, {\it Amer. Math. Monthly,} vol.~96, 1989,
pp.~125--128.

\bibitem{beuk75} F.~Beukers, The lattice points of $n$-dimensionl
tetrahedra, {\it Indag. Math.}, vol.~37, 1975, pp.~365--372.

\bibitem{chan68} K.~Chandrasekharan, {\it Introduction to Analytic
Number Theory,} Springer-Verlag, 1968.

\bibitem{cohe90}
G.~L.~Cohen, On an integer's infinitary divisors, {\it Math.
Comput.} vol.~54, 1990, pp.395--411.

\bibitem{cohe93}
G.~L.~Cohen, and P.~Hagis, Arithmetic functions associated with the
infinitary divisors of an integer, {\it Internat. J. Math. \& Math.
Sci.}, vol.~16, no.~2, 1993, pp.~373--384.

\bibitem{cohe} H.~Cohen, High precision computation of
Hardy-Littlewood constants, preprint, see
http://www.ufr-mi.u-bordeaux.fr/\,$\sim$cohen/

\bibitem{iwan04} H.~Iwaniec and E.~Kowalski, {\it Analytic Number
Theory}, AMS Colloquium Publications, 2004.

\bibitem{finc03} S.~R.~Finch, Euler totient constants, in {\it
Mathematical Constants}, Cambridge University Press, 2003,
pp.~115--118.

\bibitem{finc04} S.~R.~Finch, Unitarism and infinitarism,
on-line http://pauillac.inria.fr/algo/csolve/try.pdf

\bibitem{more00} P.~Moree, Approximation of singular series and
automata, {\it Manuscripta Math.}, vol.~101, no.~3, 2000,
pp.~385--399.

\bibitem{pede04}
J.~M.~Pedersen, Tables of aliquot cycles, 2004,
http://amicable.adsl.dk/aliquot/infper.txt

%\bibitem{poly90}
%G.~P\'{o}lya, {\it Mathematics and Plausible Reasoning}, Princeton
%University Press, 1990.

\bibitem{post88}
A.~G.~Postnikov, {\it Introduction to Analytic Number Theory,}
  Translations of Mathematical Monographs, vol.~68,
American Mathematical Society, Providence, RI, 1988.

\bibitem{prac78}
K.~Prachar, {\it Primzahlverteilung (The distribution of primes)}
Reprint of the 1957 original, Grundlehren der Mathematischen
Wissenschaften, vol.~91, Springer-Verlag, Berlin-New York, 1978.

\bibitem{redm96} D.~Redmond, {\it Number Theory, An Introduction,}
Marcel Dekker, 1996.

\bibitem{shev81} V.~S.~Abramovich-Shevelev, On an analog of the Euler
function, {\it Proc. North-Caucasus Center Acad. Sci. USSR}, no.~2,
1981, pp.~13--17 (In Russian).

\bibitem{shev82} V.~S.~Shevelev, Factorization with distinct
factors, {\it Kvant}, no.~5, 1983, p.~37 (In Russian).

\bibitem{shev96} V.~S.~Shevelev, Multiplicative functions in the
Fermi-Dirac arithmetic, {\it Izv. VUZov Sev.-Kav. Reg. Est. Nauki},
no.~4, 1996, pp.~28--43 (In Russian).

\bibitem{sloa} N.~J.~A.~Sloane, Sequence A007357$/$M4267 in The On-Line
Encyclopedia of Integer Sequences,
http://www.research.att.com/~njas/sequences/A007357.

\bibitem{sury68}
D.~Suryanarayana, The number of k-ary divisors of an integer,
{\it Monatschr. Math.} vol.~72, 1968, pp.~445--450.

\bibitem{sury70} D.~Suryanarayana, and V.~Siva Rama Prasad, The
number of $k$-free divisors of an integer, {\it Acta Arithm.},
vol.~17, 1970/1971, pp.~345--354.

\bibitem{tros53} E.~Trost, {\it Primzahlen}, Birkhauser,
 Basel-Stuttgart, 1953
(In German).

\bibitem{weis} E.~W.~Weisstein, Infinitary perfect numbers, {\it
MathWorld--A Wolfram Web Resource},
http://mathworld.wolfram.com/InfinitaryPerfectNumber.html.

\end{thebibliography}
\end{document}

%E. Landau, ?ber die zahlentheoretische Function ?(n) und ihre
%Beziehung zum Goldbachschen Satz, Nachrichten K?niglichen
%Gesellschaft der Wissenschaften zu G?ttingen, Math.-Phys. Klasse
%(1900) 177-186; Collected Works, v. 1, ed. L. Mirsky, I. J.
%Schoenberg, W. Schwarz and H. Wefelscheid, Thales Verlag, 1983, pp.
%106-115.