Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: UNSURE 0.311
X-Spam-Level: ***
X-Spam-Evidence: '*H*': 0.57; '*S*': 0.19; 'suppose': 0.07; 'here?': 0.09; 'compression': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'wrote:': 0.18; 'header:In- Reply-To:1': 0.27; 'message-id:@mail.gmail.com': 0.30; 'subject:that': 0.31; 'fri,': 0.33; "can't": 0.35; 'received:google.com': 0.35; 'representing': 0.36; 'scheme': 0.36; 'represent': 0.38; 'nov': 0.38; 'to:addr:python-list': 0.38; 'issue': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'major': 0.40; 'how': 0.40; "you've": 0.63; 'limit': 0.70; 'prime': 0.74; 'density': 0.84; 'viable': 0.84; 'average': 0.93; 'factors': 0.97; '2013': 0.98
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=RE6XpDK+5X1sfof9kC1BQtbCLpcRl9lFguXxfHtK/Pg=; b=Eg2CWNzfPiUK3SnhhX5+tDaesqTJdku6ct+s65ZGkcSm9TZ6ogf5Uz1v3tnK5LVZrG REkjzc9MHrepk2uyFhsWdFW2Kg4yURKGks2cv25iQBQYk1VqDiAdVSNoOkhU2Tg5XCOd EUe1Pb3c0Y8ojjC06nHriQP4I3zTxVFp3DXSISBdLU7M2d0piL6fGxxwbOo1viREAxqP NtkgN9efHjU8MaaiIUw3y2nojY1xlLbP+qqL2+mHy5kD1R2eRK6f8ZMd+0VDvFDZOKv0 d9lCBN+sFtxMXgft1sZFSVlDh0wYJcpWNEDavvlGmrBfJHs2zzurH5ZIBY9T74SbJlp1 PEgQ==
MIME-Version: 1.0
X-Received: by 10.68.130.36 with SMTP id ob4mr13189473pbb.180.1383895319449; Thu, 07 Nov 2013 23:21:59 -0800 (PST)
In-Reply-To: <be3h0tFr5c2U1@mid.individual.net>
References: <205bfa4f-29de-43de-be5a-72a12d77d0c9@googlegroups.com> <mailman.1835.1383162420.18130.python-list@python.org> <c73c8aa6-cac4-4f02-ae83-31cea167c172@googlegroups.com> <s9ra79dvvnd01rpuqg9hfh6bija8u2q49h@4ax.com> <9d998707-a6e9-4911-a585-c2310e4a2b31@googlegroups.com> <q7im799jqj9ap3jb94lnqka1m0hnn9bnpv@4ax.com> <CAMjeLr8jao50FSqM9pT=77in0nPNCOA8SQwHC_Jm50eiQYTs+g@mail.gmail.com> <mailman.2161.1383863216.18130.python-list@python.org> <9b62770c-7ca1-4a4d-81a5-bf7251bac957@googlegroups.com> <mailman.2171.1383877064.18130.python-list@python.org> <13c04f06-f1f2-4f67-b975-3cff28714641@googlegroups.com> <CAPTjJmpkHUQEXH8E0c8athUs8RNCEFuNVj8jDoi-zYm8+qKcnQ@mail.gmail.com> <mailman.2178.1383878604.18130.python-list@python.org> <527c6cf1$0$29983$c3e8da3$5496439d@news.astraweb.com> <be3h0tFr5c2U1@mid.individual.net>
Date: Fri, 8 Nov 2013 18:21:59 +1100
Subject: Re: Algorithm that makes maximum compression of completly diffused data.
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
X-Mailman-Approved-At: Fri, 08 Nov 2013 10:35:44 +0100
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.2199.1383903345.18130.python-list@python.org>
Lines: 18
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1383903345 news.xs4all.nl 15897 [2001:888:2000:d::a6]:33279
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:58768

On Fri, Nov 8, 2013 at 6:09 PM, Gregory Ewing
<greg.ewing@canterbury.ac.nz> wrote:
> You've got me thinking now about how viable a compression
> scheme this would be, efficiency issues aside. I suppose
> it would depend on things like the average density of primes
> and the average number of prime factors a number has.
> Any number theorists here?

Start by coming up with an efficient storage representation for the
primes. Don't forget that you can't use a bitfield, because eg 98 =
7*7*2, so you somehow need to represent that the 7 comes up twice. And
you can't limit the size of your primes (eg by representing 98 as
"\x07\x07\x02").

And that's without dealing with the major issue of _finding_ prime
factors for a large number.

ChrisA