Decomposing 40 billion integers by four tetrahedral numbers

Chung-Chiang Chou, Yuefan Deng

Research output: Contribution to journalArticle

Abstract

Based upon a computer search performed on a massively parallel supercomputer, we found that any integer n less than 40 billion (40B) but greater than 343, 867 can be written as a sum of four or fewer tetrahedral numbers. This result has established a new upper bound for a conjecture compared to an older one, 1B, obtained a year earlier. It also gives more accurate asymptotic forms for partitioning. All this improvement is a direct result of algorithmic advances in efficient memory and cpu utilizations. The heuristic complexity of the new algorithm is O(n) compared with that of the old, O(n5/3 log n).

Original languageEnglish
Pages (from-to)893-901
Number of pages9
JournalMathematics of Computation
Volume66
Issue number218
Publication statusPublished - 1997 Apr 1

Fingerprint

Tetrahedral number
Supercomputers
Data storage equipment
Integer
Supercomputer
Partitioning
Heuristics
Upper bound

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Cite this

@article{f6b3ce983bca43db8c1347444ef40335,
title = "Decomposing 40 billion integers by four tetrahedral numbers",
abstract = "Based upon a computer search performed on a massively parallel supercomputer, we found that any integer n less than 40 billion (40B) but greater than 343, 867 can be written as a sum of four or fewer tetrahedral numbers. This result has established a new upper bound for a conjecture compared to an older one, 1B, obtained a year earlier. It also gives more accurate asymptotic forms for partitioning. All this improvement is a direct result of algorithmic advances in efficient memory and cpu utilizations. The heuristic complexity of the new algorithm is O(n) compared with that of the old, O(n5/3 log n).",
author = "Chung-Chiang Chou and Yuefan Deng",
year = "1997",
month = "4",
day = "1",
language = "English",
volume = "66",
pages = "893--901",
journal = "Mathematics of Computation",
issn = "0025-5718",
publisher = "American Mathematical Society",
number = "218",

}

Decomposing 40 billion integers by four tetrahedral numbers. / Chou, Chung-Chiang; Deng, Yuefan.

In: Mathematics of Computation, Vol. 66, No. 218, 01.04.1997, p. 893-901.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Decomposing 40 billion integers by four tetrahedral numbers

AU - Chou, Chung-Chiang

AU - Deng, Yuefan

PY - 1997/4/1

Y1 - 1997/4/1

N2 - Based upon a computer search performed on a massively parallel supercomputer, we found that any integer n less than 40 billion (40B) but greater than 343, 867 can be written as a sum of four or fewer tetrahedral numbers. This result has established a new upper bound for a conjecture compared to an older one, 1B, obtained a year earlier. It also gives more accurate asymptotic forms for partitioning. All this improvement is a direct result of algorithmic advances in efficient memory and cpu utilizations. The heuristic complexity of the new algorithm is O(n) compared with that of the old, O(n5/3 log n).

AB - Based upon a computer search performed on a massively parallel supercomputer, we found that any integer n less than 40 billion (40B) but greater than 343, 867 can be written as a sum of four or fewer tetrahedral numbers. This result has established a new upper bound for a conjecture compared to an older one, 1B, obtained a year earlier. It also gives more accurate asymptotic forms for partitioning. All this improvement is a direct result of algorithmic advances in efficient memory and cpu utilizations. The heuristic complexity of the new algorithm is O(n) compared with that of the old, O(n5/3 log n).

UR - http://www.scopus.com/inward/record.url?scp=0031484553&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031484553&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0031484553

VL - 66

SP - 893

EP - 901

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 218

ER -