Paper Info
Title
Emulating primality with multiset representations of natural numbers
Abstract
Factorization results in multisets of primes and this mapping can be turned into a bijection between multisets of natural numbers and natural numbers. At the same time, simpler and more efficient bijections exist that share some interesting properties with the bijection derived from factorization. This paper describes mechanisms to emulate properties of prime numbers through isomorphisms connecting them to computationally simpler representations involving bijections from natural numbers to multisets of natural numbers. As a result, interesting automorphisms of N and emulations of the rad, Möbius and Mertens functions emerge in the world of our much simpler multiset representations. The paper is organized as a self-contained literate Haskell program. The code extracted from the paper is available as a standalone program at http://logic.cse.unt.edu/tarau/research/2011/mprimes.hs.
Year
DOI
Venue
2011
10.1007/978-3-642-23283-1_15
ICTAC
Keywords
Field
DocType
self-contained literate haskell program,efficient bijections,simpler multiset representation,standalone program,natural number,emulating primality,factorization result,interesting property,mertens function,interesting automorphisms,simpler representation
Discrete mathematics,Combinatorics,Natural number,Bijection,Prime number,Primality test,Computer science,Multiset,Bijection, injection and surjection,Factorization,Haskell
Conference
Citations 
PageRank 
References 
1
0.36
17
Authors
1
Name
Order
Citations
PageRank
Paul Tarau11529113.14