Problem Summary

A generalized Hamming number of type $T$ is a positive integer whose prime divisors are all at most $T$. For this problem we must count how many numbers $n \le L$ satisfy that condition when $T=100$ and $L=10^9$.

If we write the set of admissible numbers as $\mathcal{H}(T,L)$, then the task is to determine $|\mathcal{H}(100,10^9)|$. The key observation is that only the primes up to $T$ matter: once those primes are fixed, every allowed composite factor is already built from them.

Mathematical Approach

Let $p_1 \lt p_2 \lt \cdots \lt p_r$ be the primes not exceeding $T$. The implementations count generalized Hamming numbers by exploring the exponent choices of these primes in increasing order.

Prime Factors Are the Entire State Space

By the fundamental theorem of arithmetic, every admissible number has a unique representation

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

and the condition $n \le L$ becomes

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

So the problem is not about testing arbitrary integers one by one. It is a structured counting problem over exponent vectors $(e_1,\dots,e_r)$. Composite numbers $\le T$ do not need their own branches, because their prime factors are already among the $p_i$.

A Counting Recurrence

Define $F(i,m)$ to be the number of integers $n \le m$ whose prime factors all belong to $\{p_i,p_{i+1},\dots,p_r\}$. Then the base case is

$$F(r+1,m)=1,$$

because once no primes remain, there is exactly one completion: choose all remaining exponents to be zero. For $1 \le i \le r$, the exponent of $p_i$ can be $0,1,2,\dots$ as long as $p_i^k \le m$, so

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

This is the exact mathematics implemented by the depth-first search. Instead of storing $m$ explicitly, the code keeps the current product and lets the remaining budget be $L$ divided by that product.

Why the Depth-First Enumeration Is Exact

At recursion depth $i$, the current value has the form

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

with $x \le L$. This is the core invariant: the exponents for the first $i-1$ primes are already fixed, and only the later primes are still free. The next loop tries $x$, $x p_i$, $x p_i^2$, and so on until the limit would be exceeded.

Because primes are handled in one fixed order, every exponent vector produces exactly one root-to-leaf path. By uniqueness of prime factorization, no valid number can appear twice under different branches. When the search reaches the level after the last prime, one and only one generalized Hamming number has been fully specified, so the counter is increased by 1. The all-zero exponent choice is therefore counted automatically, giving the number $1$.

Worked Example: Type 5 Up to 100

For $T=5$, the allowed primes are $2,3,5$. If $L=100$, then

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

These seven terms correspond to the possible exponents of $2$: $2^0,2^1,\dots,2^6$. Each term is then split again by the exponent of $3$, and each of those branches is finally split by powers of $5$. Carrying the recursion through gives 34 numbers in total, namely the integers of the form $2^a3^b5^c \le 100$.

This small example is exactly the same tree structure used for type $100$ and limit $10^9$; only the list of primes and the search depth become larger.

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase pattern: first generate the relevant primes, then recursively enumerate every valid exponent combination.

Prime Generation

The implementation begins with a sieve up to $T$ and collects all primes $\le T$. For Problem 204 this yields $r=\pi(100)=25$ primes. That prime list completely determines the search tree.

Recursive State and Branches

The recursive state is naturally described by a pair $(i,x)$, where $i$ is the next prime index and $x$ is the current product already formed from earlier primes. From that state, the implementation recursively explores

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

for as long as those values stay within the limit. Moving to the next level means that the exponent of $p_i$ has been fixed and the search continues with the next prime.

Base Case and Safety Guard

When all primes have been processed, the recursion has fixed a complete exponent vector, so one valid number is counted. Before multiplying by the next prime, the implementation checks

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

which is equivalent to $x p_i \le L$. This keeps the search inside the bound and also avoids overflowing the integer type during multiplication.

Complexity Analysis

Generating the primes with a sieve costs $O(T \log\log T)$ time and $O(T)$ memory.

For the search itself, let $N=|\mathcal{H}(T,L)|$ and let $r=\pi(T)$. The recursion depth is $r$. Every node at depth $i$ is a partial product built from the first $i-1$ primes, and that partial product is itself a generalized Hamming number not exceeding $L$. Hence there are at most $N$ nodes on each depth level, giving $O(rN)$ recursive calls overall.

For the actual problem $T=100$, $r=25$, so the depth is tiny and the method is effectively output-sensitive: it spends its time enumerating precisely the valid exponent combinations rather than scanning all integers up to $10^9$. The extra memory used by the search is $O(r)$ for the recursion stack, in addition to the sieve storage.

Footnotes and References

Problemzusammenfassung

Eine verallgemeinerte Hamming-Zahl vom Typ $T$ ist eine positive ganze Zahl, deren sämtliche Primteiler höchstens $T$ sind. In diesem Problem soll gezählt werden, wie viele Zahlen $n \le L$ diese Eigenschaft besitzen, wenn $T=100$ und $L=10^9$ gilt.

Bezeichnen wir die Menge aller zulässigen Zahlen mit $\mathcal{H}(T,L)$, dann ist gesucht $|\mathcal{H}(100,10^9)|$. Entscheidend ist dabei, dass nur die Primzahlen bis $T$ wirklich relevant sind: Sobald diese Primzahlen erlaubt sind, entstehen alle zulässigen zusammengesetzten Faktoren bereits automatisch daraus.

Mathematischer Ansatz

Seien $p_1 \lt p_2 \lt \cdots \lt p_r$ die Primzahlen, die $T$ nicht überschreiten. Die Implementierungen zählen verallgemeinerte Hamming-Zahlen, indem sie die möglichen Exponenten dieser Primzahlen in aufsteigender Reihenfolge durchsuchen.

Primfaktoren bilden den gesamten Zustandsraum

Nach dem Fundamentalsatz der Arithmetik besitzt jede zulässige Zahl die eindeutige Darstellung

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

und die Schranke lautet dann schlicht

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

Das Problem besteht also nicht darin, beliebige Zahlen bis $L$ einzeln zu testen. Stattdessen zählt man Exponentenvektoren $(e_1,\dots,e_r)$, die die Produktbedingung erfüllen. Zusammengesetzte Zahlen $\le T$ brauchen keine eigenen Zweige, weil ihre Primfaktoren bereits unter den $p_i$ vorkommen.

Eine Zählrekurrenz

Sei $F(i,m)$ die Anzahl der Zahlen $n \le m$, deren Primfaktoren alle in $\{p_i,p_{i+1},\dots,p_r\}$ liegen. Dann gilt als Basisfall

$$F(r+1,m)=1,$$

denn wenn keine Primzahlen mehr übrig sind, gibt es genau eine Fortsetzung: alle verbleibenden Exponenten werden gleich null gewählt. Für $1 \le i \le r$ darf der Exponent von $p_i$ die Werte $0,1,2,\dots$ annehmen, solange $p_i^k \le m$ bleibt. Also folgt

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

Genau diese Rekurrenz steckt im Tiefensuchbaum. Der Code speichert nicht explizit $m$, sondern hält das aktuelle Produkt fest; das verbleibende Budget ist dann $L$ geteilt durch dieses Produkt.

Warum die Tiefensuche exakt zählt

In Rekursionstiefe $i$ hat der aktuelle Wert die Form

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

wobei stets $x \le L$ gilt. Das ist die zentrale Invariante: Die Exponenten der ersten $i-1$ Primzahlen sind bereits festgelegt, nur die späteren Primzahlen bleiben noch frei. Die nächste Schleife probiert dann $x$, $x p_i$, $x p_i^2$ und so weiter, bis die Grenze überschritten würde.

Weil die Primzahlen in einer festen Reihenfolge behandelt werden, erzeugt jeder Exponentenvektor genau einen Pfad von der Wurzel zu einem Blatt. Aufgrund der Eindeutigkeit der Primfaktorzerlegung kann keine zulässige Zahl in zwei verschiedenen Zweigen auftreten. Erreicht die Suche die Ebene nach der letzten Primzahl, ist genau eine verallgemeinerte Hamming-Zahl vollständig bestimmt, und der Zähler wird um 1 erhöht. Dadurch wird auch die Zahl $1$ automatisch mitgezählt.

Durchgerechnetes Beispiel: Typ 5 bis 100

Für $T=5$ sind die erlaubten Primzahlen $2,3,5$. Bei $L=100$ erhält man

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

Diese sieben Summanden entsprechen den möglichen Exponenten von $2$: $2^0,2^1,\dots,2^6$. Jeder Summand wird anschließend nach den Exponenten von $3$ weiter verzweigt, und zuletzt nach den Potenzen von $5$. Führt man die Rekursion vollständig aus, erhält man insgesamt 34 Zahlen der Form $2^a3^b5^c \le 100$.

Genau dieselbe Baumstruktur wird auch beim eigentlichen Problem verwendet; lediglich die Primliste ist länger und die Rekursion reicht tiefer.

Wie der Code arbeitet

Die C++-, Python- und Java-Implementierungen folgen alle demselben Muster: Zuerst werden die relevanten Primzahlen erzeugt, anschließend werden alle zulässigen Exponentenkombinationen rekursiv durchlaufen.

Primzahlen vorberechnen

Zu Beginn erzeugt die Implementierung mit einem Sieb alle Primzahlen bis $T$. Für Problem 204 ergibt das $r=\pi(100)=25$ Primzahlen. Diese Liste bestimmt den gesamten Suchbaum.

Rekursiver Zustand und Verzweigungen

Der Rekursionszustand lässt sich als Paar $(i,x)$ beschreiben, wobei $i$ den Index der nächsten Primzahl bezeichnet und $x$ das bereits aus früheren Primzahlen gebildete Produkt ist. Von dort aus untersucht die Implementierung rekursiv die Werte

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

solange sie innerhalb der Schranke bleiben. Der Übergang zur nächsten Ebene bedeutet, dass der Exponent von $p_i$ festgelegt wurde und nun die nächste Primzahl an der Reihe ist.

Basisfall und sichere Multiplikation

Sobald alle Primzahlen abgearbeitet sind, hat die Rekursion einen vollständigen Exponentenvektor festgelegt, also wird genau eine gültige Zahl gezählt. Vor jeder weiteren Multiplikation prüft die Implementierung

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

was äquivalent zu $x p_i \le L$ ist. Dadurch bleibt die Suche innerhalb der Schranke und vermeidet zugleich Überläufe im Ganzzahltyp.

Komplexitätsanalyse

Das Erzeugen der Primzahlen mit einem Sieb kostet $O(T \log\log T)$ Zeit und $O(T)$ Speicher.

Für die Suche selbst bezeichne $N=|\mathcal{H}(T,L)|$ die Anzahl der gesuchten Hamming-Zahlen und $r=\pi(T)$ die Zahl der verwendeten Primzahlen. Die Rekursionstiefe beträgt $r$. Jeder Knoten in Tiefe $i$ ist ein Teilprodukt aus den ersten $i-1$ Primzahlen und damit selbst schon eine verallgemeinerte Hamming-Zahl $\le L$. Daher gibt es auf jeder Tiefe höchstens $N$ Knoten, insgesamt also $O(rN)$ Rekursionsaufrufe.

Für $T=100$ gilt $r=25$, also ist die Tiefe sehr klein. Praktisch ist das Verfahren damit ausgabesensitiv: Es investiert seine Zeit in die tatsächlich zulässigen Exponentenkombinationen, statt alle Zahlen bis $10^9$ zu testen. Der zusätzliche Suchspeicher beträgt $O(r)$ für den Rekursionsstapel, zuzüglich des Speichers für das Sieb.

Fußnoten und Quellen

Problem Özeti

Tipi $T$ olan genelleştirilmiş Hamming sayısı, bütün asal bölenleri en fazla $T$ olan pozitif bir tam sayıdır. Bu problemde $T=100$ ve $L=10^9$ için $n \le L$ koşulunu da sağlayan böyle sayıların kaç tane olduğu istenir.

Uygun sayıların kümesini $\mathcal{H}(T,L)$ ile gösterirsek hedef $|\mathcal{H}(100,10^9)|$ değerini bulmaktır. Kritik nokta şudur: aslında yalnızca $T$'ye kadar olan asallar önemlidir. Bu asallar izinli olduktan sonra, izinli bütün bileşik çarpanlar zaten onlardan otomatik olarak oluşur.

Matematiksel Yaklaşım

$T$'yi aşmayan asalları $p_1 \lt p_2 \lt \cdots \lt p_r$ şeklinde yazalım. Uygulamalar, bu asalların üslerini artan sırayla seçen bir arama üzerinden genelleştirilmiş Hamming sayılarını sayar.

Durum Uzayı Tamamen Asal Çarpanlardan Oluşur

Aritmetiğin temel teoremine göre her uygun sayı

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

şeklinde tek biçimde yazılır ve sınır koşulu da

$$\prod_{i=1}^{r} p_i^{e_i} \le L$$

olur. Dolayısıyla problem, $1$'den $L$'ye kadar bütün sayıları tek tek test etmek değildir; asıl iş, bu eşitsizliği sağlayan üs vektörlerini $(e_1,\dots,e_r)$ saymaktır. $T$'den küçük ya da eşit bileşik sayılar için ayrıca dal açmaya gerek yoktur, çünkü onların asal çarpanları zaten $p_i$ listesinde yer alır.

DFS'nin Gizlediği Sayma Bağıntısı

$F(i,m)$ değerini, asal çarpanları yalnızca $\{p_i,p_{i+1},\dots,p_r\}$ kümesinden gelen ve $m$'i aşmayan sayıların adedi olarak tanımlayalım. Taban durum

$$F(r+1,m)=1$$

şeklindedir; çünkü artık hiç asal kalmadığında yapılacak tek şey, kalan bütün üsleri sıfır seçmektir. $1 \le i \le r$ için $p_i$'nin üssü, $p_i^k \le m$ olduğu sürece $0,1,2,\dots$ değerlerini alabilir. Bu yüzden

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right)$$

bağıntısı elde edilir. Derinlik öncelikli aramanın yaptığı şey tam olarak budur. Kod, $m$ değerini ayrı tutmak yerine mevcut çarpımı saklar; geriye kalan bütçe de $L$'nin bu çarpıma bölünmesiyle belirlenir.

Neden Her Geçerli Sayı Tam Bir Kez Sayılır?

Özyinelemenin $i$. seviyesinde mevcut değer

$$x=\prod_{j=1}^{i-1} p_j^{e_j}$$

biçimindedir ve her zaman $x \le L$ koşulunu sağlar. Temel değişmez şudur: ilk $i-1$ asalın üsleri artık sabittir; sadece sonraki asalların üsleri seçilecektir. Sonraki döngü bu yüzden $x$, $x p_i$, $x p_i^2$, ... değerlerini, sınır aşılana kadar sırayla dener.

Asallar tek bir sabit sırada işlendiği için her üs vektörü kökten yaprağa giden tam bir yola karşılık gelir. Asal çarpanlara ayrışımın tekilliği sayesinde aynı sayı iki farklı daldan üretilemez. Arama son asalın da ötesindeki seviyeye ulaştığında tek bir genelleştirilmiş Hamming sayısı tamamen belirlenmiş olur ve sayaç 1 artırılır. Böylece bütün üslerin sıfır olduğu yol da otomatik olarak sayılır; bu da $1$ sayısını kapsar.

Çalışılmış Örnek: Tip 5 ve Üst Sınır 100

$T=5$ için izinli asallar $2,3,5$'tir. $L=100$ olduğunda

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1)$$

yazılır. Bu yedi terim, $2$'nin mümkün üslerine yani $2^0,2^1,\dots,2^6$ seçimlerine karşılık gelir. Her terim sonra $3$'ün üslerine göre, onların her biri de son olarak $5$'in üslerine göre dallanır. Özyineleme tamamlandığında $2^a3^b5^c \le 100$ biçimindeki sayıların toplamı 34 olur.

Gerçek problemde kullanılan ağaç tam olarak aynıdır; yalnızca asal listesi daha uzundur ve aramanın derinliği artar.

Kod Nasıl Çalışır

C++, Python ve Java uygulamaları aynı iki aşamalı yapıyı izler: önce gerekli asalları üretir, sonra da bütün geçerli üs kombinasyonlarını özyinelemeli olarak dolaşır.

Asal Ön Hesabı

İlk aşamada $T$'ye kadar bir elekle bütün asallar çıkarılır. Problem 204 için bu, $r=\pi(100)=25$ asal verir. Bu liste arama ağacının tamamını belirler.

Özyinelemeli Durum ve Dallanma

Aramanın durumu doğal olarak $(i,x)$ çifti ile açıklanır: $i$ sıradaki asalın indisi, $x$ ise daha önceki asallardan oluşmuş mevcut çarpımdır. Bu durumdan itibaren uygulama

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

değerlerini sınır içinde kaldıkları sürece özyinelemeli olarak dener. Sonraki seviyeye geçmek, $p_i$'nin üssünün sabitlendiği ve sıranın bir sonraki asala geçtiği anlamına gelir.

Taban Durum ve Güvenli Çarpma Koruması

Bütün asallar işlendiğinde özyineleme tam bir üs vektörü kurmuştur; dolayısıyla bir geçerli sayı sayılır. Sonraki asal ile çarpmadan önce uygulama

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor$$

koşulunu kontrol eder; bu, $x p_i \le L$ ile eşdeğerdir. Böylece hem sınır aşılmaz hem de tam sayı çarpımında taşma riski önlenir.

Karmaşıklık Analizi

Asalları elekle üretmenin maliyeti $O(T \log\log T)$ zaman ve $O(T)$ bellektir.

Arama için $N=|\mathcal{H}(T,L)|$ ve $r=\pi(T)$ diyelim. Özyineleme derinliği $r$'dir. Derinlik $i$'deki her düğüm, ilk $i-1$ asal kullanılarak kurulmuş bir kısmi çarpımdır ve bu kısmi çarpım zaten $L$'yi aşmayan bir genelleştirilmiş Hamming sayısıdır. Bu nedenle her derinlikte en fazla $N$ düğüm bulunur; toplam çağrı sayısı da $O(rN)$ olur.

Gerçek problemde $T=100$ olduğu için $r=25$ gibi çok küçük bir derinlik vardır. Bu yüzden yöntem pratikte output-sensitive davranır: zamanı, gerçekten geçerli olan üs kombinasyonlarını üretmeye harcar; $10^9$'a kadar tüm sayıları taramaz. Ek arama belleği, özyineleme yığını için $O(r)$ ve buna ek olarak elek depolamasıdır.

Dipnotlar ve Kaynaklar

Resumen del Problema

Un número de Hamming generalizado de tipo $T$ es un entero positivo cuyos divisores primos son todos menores o iguales que $T$. En este problema hay que contar cuántos números $n \le L$ cumplen esa condición cuando $T=100$ y $L=10^9$.

Si denotamos por $\mathcal{H}(T,L)$ el conjunto de valores admisibles, el objetivo es calcular $|\mathcal{H}(100,10^9)|$. La observación decisiva es que solo importan los primos hasta $T$: una vez permitidos esos primos, cualquier factor compuesto permitido ya está formado por ellos.

Enfoque Matemático

Sea $p_1 \lt p_2 \lt \cdots \lt p_r$ la lista de primos no mayores que $T$. Las implementaciones cuentan los números de Hamming generalizados explorando, en orden creciente, los exponentes posibles de esos primos.

Los factores primos describen todo el espacio del problema

Por el teorema fundamental de la aritmética, todo número admisible posee una representación única

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

y la restricción del problema pasa a ser

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

Por tanto, no hace falta probar uno por uno todos los enteros hasta $L$. Lo que realmente se cuenta son los vectores de exponentes $(e_1,\dots,e_r)$ que satisfacen esa desigualdad. Los compuestos $\le T$ no necesitan ramas propias, porque sus factores primos ya están incluidos entre los $p_i$.

La recurrencia de conteo

Definamos $F(i,m)$ como el número de enteros $n \le m$ cuyos factores primos pertenecen al conjunto $\{p_i,p_{i+1},\dots,p_r\}$. El caso base es

$$F(r+1,m)=1,$$

porque, cuando ya no quedan primos por considerar, solo existe una forma de completar la construcción: fijar todos los exponentes restantes en cero. Para $1 \le i \le r$, el exponente de $p_i$ puede ser $0,1,2,\dots$ mientras $p_i^k \le m$. Por eso

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

Esa es exactamente la matemática que implementa la búsqueda en profundidad. El código no almacena $m$ de forma explícita; en su lugar mantiene el producto actual y deja que el presupuesto restante sea $L$ dividido por ese producto.

Por qué la enumeración DFS es correcta

En la profundidad $i$ de la recursión, el valor actual tiene la forma

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

con $x \le L$. Ese es el invariante central: los exponentes de los primeros $i-1$ primos ya quedaron fijados, mientras que los de los primos posteriores todavía están libres. El siguiente bucle prueba entonces $x$, $x p_i$, $x p_i^2$, y así sucesivamente, hasta que una multiplicación adicional superaría el límite.

Como los primos se procesan en un único orden fijo, cada vector de exponentes genera exactamente un camino desde la raíz hasta una hoja. La unicidad de la factorización prima impide que el mismo número válido aparezca en ramas diferentes. Cuando la búsqueda alcanza el nivel posterior al último primo, una y solo una cantidad de Hamming generalizada ha quedado completamente determinada, así que el contador se incrementa en 1. De este modo, el camino en el que todos los exponentes valen cero cuenta automáticamente al número $1$.

Ejemplo Desarrollado: Tipo 5 hasta 100

Para $T=5$, los primos permitidos son $2,3,5$. Si $L=100$, se obtiene

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

Esos siete sumandos corresponden a los exponentes posibles de $2$: $2^0,2^1,\dots,2^6$. Cada sumando se vuelve a descomponer según la potencia de $3$, y cada una de esas ramas se divide finalmente por las potencias de $5$. Al completar toda la recurrencia aparecen 34 números de la forma $2^a3^b5^c \le 100$.

El problema real utiliza exactamente el mismo árbol de decisiones; solo crecen la lista de primos y la profundidad de la búsqueda.

Cómo Funciona el Código

Las implementaciones en C++, Python y Java siguen el mismo esquema en dos etapas: primero generan los primos relevantes y luego enumeran recursivamente todas las combinaciones válidas de exponentes.

Generación de primos

La implementación comienza con un tamiz hasta $T$ y recopila todos los primos $\le T$. Para el Problema 204 esto produce $r=\pi(100)=25$ primos. Esa lista fija por completo la estructura del árbol de búsqueda.

Estado recursivo y ramificación

El estado recursivo se describe de forma natural mediante el par $(i,x)$, donde $i$ es el índice del siguiente primo y $x$ es el producto actual ya construido con primos anteriores. Desde ese estado la implementación explora recursivamente

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

mientras esos valores sigan dentro del límite. Pasar al siguiente nivel significa que el exponente de $p_i$ ya quedó fijado y la búsqueda continúa con el primo siguiente.

Caso base y control seguro de multiplicación

Cuando todos los primos han sido procesados, la recursión ya fijó un vector completo de exponentes, así que se cuenta exactamente un número válido. Antes de multiplicar por el primo siguiente, la implementación comprueba

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

lo cual equivale a $x p_i \le L$. Esa prueba mantiene la búsqueda dentro del rango y además evita desbordamientos en la aritmética entera.

Análisis de Complejidad

Generar los primos con un tamiz cuesta $O(T \log\log T)$ en tiempo y $O(T)$ en memoria.

Para la búsqueda, sea $N=|\mathcal{H}(T,L)|$ y sea $r=\pi(T)$. La profundidad de la recursión es $r$. Cada nodo en la profundidad $i$ es un producto parcial construido con los primeros $i-1$ primos, y ese producto parcial ya es por sí mismo un número de Hamming generalizado no mayor que $L$. Por ello hay como máximo $N$ nodos por nivel, y el número total de llamadas recursivas es $O(rN)$.

En el problema concreto $T=100$, se tiene $r=25$, así que la profundidad es muy pequeña. En la práctica el método es sensible a la salida: dedica su trabajo a enumerar exactamente las combinaciones válidas de exponentes en vez de recorrer todos los enteros hasta $10^9$. La memoria adicional de la búsqueda es $O(r)$ para la pila recursiva, además del espacio del tamiz.

Notas y Referencias

问题概述

类型为 $T$ 的广义 Hamming 数，是指所有素因子都不超过 $T$ 的正整数。本题要求在 $T=100$、$L=10^9$ 时，统计满足 $n \le L$ 的这类整数共有多少个。

如果把所有满足条件的数记为集合 $\mathcal{H}(T,L)$，那么目标就是求出 $|\mathcal{H}(100,10^9)|$。这里最关键的观察是：真正需要处理的对象只有不超过 $T$ 的素数。一旦这些素数被允许，所有合法的合数因子都已经自动包含在内。

数学方法

设 $p_1 \lt p_2 \lt \cdots \lt p_r$ 是所有不超过 $T$ 的素数。三份实现都按照这些素数的升序，逐步决定各自的指数，从而完成计数。

状态空间完全由素数指数决定

根据算术基本定理，每一个合法的数都能唯一地写成

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

并且题目的上界条件就是

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

因此，这不是一个把 $1$ 到 $L$ 全部整数逐个试除的题目，而是一个对指数向量 $(e_1,\dots,e_r)$ 进行结构化计数的问题。所有 $\le T$ 的合数都不需要单独处理，因为它们的素因子本来就已经包含在 $p_i$ 这份列表里。

DFS 背后的递推关系

定义 $F(i,m)$ 为：所有不超过 $m$、且素因子只来自集合 $\{p_i,p_{i+1},\dots,p_r\}$ 的整数个数。其边界条件为

$$F(r+1,m)=1,$$

因为当没有素数可选时，只剩下一种完成方式，也就是把剩余所有指数都取为 0。对于 $1 \le i \le r$，素数 $p_i$ 的指数可以取 $0,1,2,\dots$，只要 $p_i^k \le m$。于是有

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

这正是深度优先搜索所实现的数学内容。代码并不显式保存参数 $m$，而是保存当前已经构造出的乘积；剩余预算自然就是 $L$ 除以这个当前乘积。

为什么这种枚举既不重不漏

在递归深度 $i$ 时，当前值一定形如

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

并始终满足 $x \le L$。这就是核心不变量：前 $i-1$ 个素数的指数已经完全固定，后面的素数指数还没有决定。于是下一层循环会依次尝试 $x$、$x p_i$、$x p_i^2$、$x p_i^3$ 等候选，直到再乘一次就会超出上界为止。

由于素数总是按固定顺序处理，每个指数向量都只会对应一条从根到叶的路径。又因为素因子分解是唯一的，所以同一个合法整数不可能在不同分支中被重复生成。当递归走到最后一个素数之后时，说明一个完整的指数向量已经确定，于是计数器加 1。所有指数都取 0 的那条路径也会被自然计入，因此数字 $1$ 自动包含在答案中。

具体例子：类型 5，范围到 100

若 $T=5$，允许的素数就是 $2,3,5$。当 $L=100$ 时，有

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

这七项对应的是 $2$ 的七种可能指数，即 $2^0,2^1,\dots,2^6$。随后每一项再按 $3$ 的指数继续拆分，而每个分支最后再按 $5$ 的幂次继续拆分。把整棵递归树展开以后，可以得到共有 34 个形如 $2^a3^b5^c \le 100$ 的数。

真正的 Problem 204 使用的正是同一套树状结构，只不过素数列表更长，递归深度也更大而已。

代码如何工作

C++、Python 和 Java 实现都遵循完全相同的两步流程：先生成需要的素数，再递归枚举所有合法的指数组合。

素数预处理

实现先对 $T$ 做一次筛法，收集所有不超过 $T$ 的素数。对本题来说，这会得到 $r=\pi(100)=25$ 个素数。这份素数表决定了整棵搜索树的结构。

递归状态与分支展开

递归状态可以自然地写成 $(i,x)$：其中 $i$ 表示下一个要处理的素数下标，$x$ 表示前面那些素数已经形成的当前乘积。从这个状态出发，实现会递归探索

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

只要这些值仍然不超过上界即可。进入下一层，就意味着 $p_i$ 的指数已经确定，之后转去处理下一个素数。

递归终点与安全乘法判断

当所有素数都已经处理完时，说明一个完整的指数向量已经构造完毕，因此恰好计入一个合法整数。每次尝试继续乘上下一个素数之前，实现都会检查

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

这与 $x p_i \le L$ 完全等价。这个判断既保证搜索不会越界，也避免了整数乘法时的溢出风险。

复杂度分析

筛出素数的代价是 $O(T \log\log T)$ 时间和 $O(T)$ 空间。

对递归搜索而言，记 $N=|\mathcal{H}(T,L)|$，记 $r=\pi(T)$。递归深度就是 $r$。深度 $i$ 上的每个节点，都是由前 $i-1$ 个素数构成的一个部分乘积，而这个部分乘积本身已经是一个不超过 $L$ 的广义 Hamming 数。因此每一层至多有 $N$ 个节点，总递归调用数可以界定为 $O(rN)$。

在本题中 $T=100$，所以 $r=25$，递归深度非常小。实际运行时，这是一种典型的输出敏感算法：它的主要工作就是枚举真正有效的指数组合，而不是扫描到 $10^9$ 的所有整数。额外搜索空间为递归栈的 $O(r)$，再加上筛法所需的存储。

脚注与参考资料

Краткое описание задачи

Обобщенное число Хэмминга типа $T$ — это положительное целое число, все простые делители которого не превосходят $T$. В этой задаче нужно посчитать, сколько таких чисел $n \le L$ существует при $T=100$ и $L=10^9$.

Если обозначить множество допустимых чисел через $\mathcal{H}(T,L)$, то требуется найти $|\mathcal{H}(100,10^9)|$. Главная идея состоит в том, что важны только простые числа до $T$: как только они разрешены, все допустимые составные множители уже автоматически получаются из них.

Математический подход

Пусть $p_1 \lt p_2 \lt \cdots \lt p_r$ — все простые числа, не превосходящие $T$. Реализации считают обобщенные числа Хэмминга, перебирая возможные показатели степеней этих простых в возрастающем порядке.

Всё сводится к векторам показателей

По основной теореме арифметики каждое допустимое число единственным образом представляется в виде

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

а ограничение задачи превращается в условие

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

Значит, не нужно проверять подряд все числа до $L$. Нужно посчитать количество векторов $(e_1,\dots,e_r)$, удовлетворяющих этому неравенству. Составные числа $\le T$ не требуют отдельных ветвей, потому что их простые делители уже входят в список $p_i$.

Рекуррентная формула подсчета

Определим $F(i,m)$ как число целых $n \le m$, простые делители которых лежат только в множестве $\{p_i,p_{i+1},\dots,p_r\}$. Базовый случай таков:

$$F(r+1,m)=1,$$

потому что если простых больше не осталось, то есть ровно один способ завершить построение: выбрать все оставшиеся показатели равными нулю. Для $1 \le i \le r$ показатель при $p_i$ может принимать значения $0,1,2,\dots$, пока выполняется $p_i^k \le m$. Поэтому

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

Именно эта формула скрыта внутри поиска в глубину. Код не хранит параметр $m$ напрямую; вместо этого он хранит текущее произведение, а оставшийся запас определяется как $L$, деленное на это произведение.

Почему DFS считает точно и без повторов

На глубине рекурсии $i$ текущее значение имеет вид

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

причем всегда сохраняется инвариант $x \le L$. Это и есть ключевой инвариант: показатели у первых $i-1$ простых уже зафиксированы, а показатели у более поздних простых еще предстоит выбрать. Следующий цикл перебирает значения $x$, $x p_i$, $x p_i^2$ и так далее, пока следующая операция умножения не вышла бы за предел $L$.

Поскольку простые рассматриваются в одном фиксированном порядке, каждому вектору показателей соответствует ровно один путь от корня к листу. Единственность разложения на простые множители исключает появление одного и того же допустимого числа в разных ветвях. Когда рекурсия доходит до уровня после последнего простого, один и только один обобщенный номер Хэмминга уже полностью определен, и счетчик увеличивается на 1. Тем самым автоматически учитывается и число $1$, соответствующее нулевым показателям у всех простых.

Разобранный пример: тип 5 и граница 100

При $T=5$ разрешенные простые равны $2,3,5$. Если $L=100$, то получаем

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

Эти семь слагаемых соответствуют возможным степеням числа $2$: $2^0,2^1,\dots,2^6$. Затем каждое слагаемое дальше расщепляется по степеням числа $3$, а каждая из получившихся ветвей — по степеням числа $5$. Если довести рекурсию до конца, получится 34 числа вида $2^a3^b5^c \le 100$.

В полной задаче используется ровно та же структура дерева; увеличиваются только список простых и глубина рекурсии.

Как работает код

Реализации на C++, Python и Java следуют одной и той же двухэтапной схеме: сначала строят список нужных простых чисел, затем рекурсивно перебирают все допустимые комбинации показателей.

Построение списка простых

Сначала реализация запускает решето до $T$ и собирает все простые $\le T$. Для Problem 204 это дает $r=\pi(100)=25$ простых чисел. Именно этот список полностью задает структуру дерева поиска.

Рекурсивное состояние и ветвление

Состояние рекурсии удобно описывать парой $(i,x)$, где $i$ — индекс следующего простого, а $x$ — текущее произведение, уже составленное из предыдущих простых. Из этого состояния реализация рекурсивно рассматривает

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

пока эти значения не превосходят лимит. Переход на следующий уровень означает, что показатель для $p_i$ уже выбран, и обработка продолжается со следующим простым.

Базовый случай и безопасная проверка умножения

Когда все простые уже обработаны, рекурсия зафиксировала полный вектор показателей, а значит найдено ровно одно допустимое число. Перед тем как умножить на очередное простое, реализация проверяет условие

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

которое эквивалентно $x p_i \le L$. Эта проверка одновременно удерживает поиск в допустимых пределах и предотвращает переполнение целочисленного типа.

Анализ сложности

Построение списка простых через решето требует $O(T \log\log T)$ времени и $O(T)$ памяти.

Для самой рекурсии обозначим через $N=|\mathcal{H}(T,L)|$ число искомых значений, а через $r=\pi(T)$ — количество разрешенных простых. Глубина рекурсии равна $r$. Каждый узел на глубине $i$ представляет частичное произведение из первых $i-1$ простых, а такое произведение уже само является обобщенным числом Хэмминга, не превосходящим $L$. Следовательно, на каждом уровне не более $N$ узлов, и общее число рекурсивных вызовов оценивается как $O(rN)$.

В реальной задаче $T=100$, поэтому $r=25$, то есть глубина очень мала. На практике алгоритм является выходно-чувствительным: он тратит время на перечисление именно допустимых комбинаций показателей, а не на просмотр всех чисел до $10^9$. Дополнительная память поиска равна $O(r)$ для стека рекурсии плюс память, необходимая решету.

Сноски и ссылки

ملخص المسألة

عدد Hamming المعمّم من النوع $T$ هو عدد صحيح موجب تكون جميع قواسِمه الأولية أقل من أو تساوي $T$. في هذه المسألة نريد عدّ جميع الأعداد $n \le L$ التي تحقق هذا الشرط عندما $T=100$ و$L=10^9$.

إذا رمزنا إلى مجموعة الأعداد المسموح بها بالرمز $\mathcal{H}(T,L)$، فالمطلوب هو إيجاد $|\mathcal{H}(100,10^9)|$. الفكرة الحاسمة هي أن ما يهم فعليًا هو الأوليات التي لا تتجاوز $T$ فقط؛ فمتى سُمِح بهذه الأوليات، تصبح جميع العوامل المركبة المسموح بها ناتجة عنها تلقائيًا.

المنهج الرياضي

لنكتب الأوليات التي لا تتجاوز $T$ على الصورة $p_1 \lt p_2 \lt \cdots \lt p_r$. تعتمد التطبيقات على عدّ أعداد Hamming المعمّمة عبر استكشاف اختيارات الأسس لهذه الأوليات بترتيب تصاعدي.

فضاء الحالات تحدده الأسس الأولية بالكامل

بحسب المبرهنة الأساسية للحساب، كل عدد مقبول يملك تمثيلًا وحيدًا من الشكل

$$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$$

ويتحول قيد المسألة إلى

$$\prod_{i=1}^{r} p_i^{e_i} \le L.$$

إذن لسنا أمام مسألة تفحص الأعداد من $1$ إلى $L$ واحدًا واحدًا، بل أمام مسألة عدّ منظّم لمتجهات الأسس $(e_1,\dots,e_r)$ التي تحقق هذا الشرط. كما أن الأعداد المركبة $\le T$ لا تحتاج إلى فروع مستقلة، لأن عواملها الأولية موجودة أصلًا ضمن القائمة $p_i$.

العلاقة العودية التي ينفذها البحث

لنعرّف $F(i,m)$ بأنه عدد الأعداد $n \le m$ التي تنتمي جميع عواملها الأولية إلى المجموعة $\{p_i,p_{i+1},\dots,p_r\}$. حالة الأساس هي

$$F(r+1,m)=1,$$

لأنه عندما لا يبقى أي أولي للاختيار، توجد طريقة واحدة فقط لإكمال البناء: جعل جميع الأسس المتبقية مساوية للصفر. أما عندما $1 \le i \le r$، فإن أسّ $p_i$ يمكن أن يكون $0,1,2,\dots$ ما دام $p_i^k \le m$. لذلك نحصل على

$$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$$

هذه هي الصيغة الرياضية الدقيقة الكامنة داخل البحث بالعمق. التنفيذ لا يخزن $m$ مباشرة، بل يحتفظ بالجداء الحالي، ويصبح الهامش المتبقي مساويًا لـ $L$ مقسومًا على ذلك الجداء.

لماذا يعدّ DFS كل عدد مرة واحدة فقط

عند العمق $i$ من الاستدعاء العودي يكون المقدار الحالي على الصورة

$$x=\prod_{j=1}^{i-1} p_j^{e_j},$$

مع المحافظة دائمًا على الشرط $x \le L$. هذا هو الثابت الأساسي: أسس الأوليات $i-1$ الأولى قد حُددت بالفعل، بينما تبقى أسس الأوليات اللاحقة غير مختارة بعد. لذا تجرّب الحلقة التالية القيم $x$، ثم $x p_i$، ثم $x p_i^2$، وهكذا إلى أن تؤدي الضربة التالية إلى تجاوز الحد.

وبما أن الأوليات تُعالَج وفق ترتيب ثابت واحد، فإن كل متجه أسس يقابل مسارًا واحدًا فقط من الجذر إلى ورقة. كما أن فرادة التحليل إلى عوامل أولية تمنع ظهور العدد نفسه في أكثر من فرع. وعندما يصل البحث إلى المستوى الذي يلي آخر أولي، يكون قد تم تحديد عدد Hamming معمّم واحد تحديدًا كاملًا، فيزاد العداد بمقدار 1. ومن ثم فإن المسار الذي تكون فيه جميع الأسس صفرًا يُحسب تلقائيًا، أي إن العدد $1$ داخل في الناتج دون معاملة خاصة.

مثال عملي: النوع 5 حتى 100

إذا كان $T=5$، فالأوليات المسموح بها هي $2,3,5$. وعندما $L=100$ نحصل على

$$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$$

تمثل هذه الحدود السبعة الأسس الممكنة للعدد $2$، أي $2^0,2^1,\dots,2^6$. ثم ينقسم كل حد بحسب أسّ $3$، وبعد ذلك تنقسم كل شعبة أخيرًا بحسب قوى $5$. وعند إكمال الشجرة كلها نحصل على 34 عددًا من الصورة $2^a3^b5^c \le 100$.

البنية المستعملة في المسألة الأصلية هي البنية نفسها تمامًا؛ الاختلاف فقط أن قائمة الأوليات أطول وعمق البحث أكبر.

كيف يعمل الكود

تتبع تطبيقات C++ وPython وJava النمط نفسه على مرحلتين: أولًا توليد الأوليات المطلوبة، ثم تعداد جميع تراكيب الأسس الصحيحة بطريقة عودية.

توليد الأوليات

يبدأ التنفيذ بتطبيق غربال حتى $T$ ثم يجمع كل الأوليات $\le T$. في Problem 204 يعطي ذلك $r=\pi(100)=25$ أوليًا. هذه القائمة وحدها تحدد شكل شجرة البحث.

الحالة العودية والتفرعات

يمكن وصف حالة العودية طبيعيًا بالزوج $(i,x)$، حيث $i$ هو فهرس الأولي التالي و$x$ هو الجداء الحالي المتكوّن من الأوليات السابقة. انطلاقًا من هذه الحالة يستكشف التنفيذ القيم

$$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$$

ما دامت لا تتجاوز الحد الأعلى. والانتقال إلى المستوى التالي يعني أن أسّ $p_i$ قد ثُبّت، وأن الدور ينتقل إلى الأولي التالي.

حالة النهاية وحارس الضرب الآمن

عندما تنتهي معالجة جميع الأوليات، تكون العودية قد ثبتت متجه أسس كاملًا، وبالتالي يُحسب عدد صحيح واحد صالح. وقبل الضرب في الأولي التالي، يتحقق التنفيذ من الشرط

$$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$$

وهو مكافئ تمامًا للشرط $x p_i \le L$. هذا الاختبار يبقي البحث داخل الحد المسموح ويمنع كذلك تجاوز سعة النوع العددي أثناء الضرب.

تحليل التعقيد

توليد الأوليات بواسطة الغربال يكلف $O(T \log\log T)$ زمنًا و$O(T)$ ذاكرة.

أما في البحث نفسه، فإذا رمزنا إلى عدد القيم المطلوبة بـ $N=|\mathcal{H}(T,L)|$ وإلى عدد الأوليات بـ $r=\pi(T)$، فإن عمق العودية يساوي $r$. وكل عقدة عند العمق $i$ تمثل جداءً جزئيًا مكوّنًا من الأوليات $i-1$ الأولى، وهذا الجداء الجزئي هو نفسه عدد Hamming معمّم لا يتجاوز $L$. لذلك يوجد على الأكثر $N$ عقد في كل مستوى، ويصبح عدد الاستدعاءات الكلي من رتبة $O(rN)$.

في هذه المسألة تحديدًا لدينا $T=100$، ومن ثم $r=25$، أي إن العمق صغير جدًا. عمليًا تعد هذه خوارزمية حساسة لحجم المخرجات: فهي تنفق وقتها على توليد تراكيب الأسس الصحيحة فعلًا بدلًا من فحص جميع الأعداد حتى $10^9$. والذاكرة الإضافية للبحث هي $O(r)$ لمكدس العودية، إضافة إلى ذاكرة الغربال.