here you can talk about your most recent finds regarding dubs theory, I will start with the well know ``dubsless primes'':
- let к(n) be the number of bases in which n has dubs excluding base 1 and base n-1 as these are trivial, we shall call n a dubsless number if к(n)=0 and n>3
- the dubsless numbers up to 10000 are 5, 6, 29, 41, 61, 113, 317, 509, 569, 761, 797, 1213, 1229, 2617, 5297, 6221 and 8017. it turns out that all of these numbers except 6 are prime, and up to 10 million all except 6 are prime, we call these primes the ``dubsless primes'' a new kind of primes. this raises the following questions in dubs theory:
- is the set of dubsless numbers/primes infinite? - is 6 the only non prime dubsless number?
Name:
Anonymous2016-03-23 17:29
I wrote a bit of code, including a decision procedure for dubs that doesn't compute its digit expansion. The way it works is, for a number n and a base b, either n has at least two trailing zeros, in which case it contains b's prime factorization twice, or it has two trailing symbols that aren't zeros, in which case it's k * (b + 1) away from a number with two or more trailing zeros for some k. This lets us test for dubs-ness in a base by knowing only its prime factorization and a few constants (k * (b + 1) for k between 1 and b - 1).
import Data.List hiding (union) import Math.NumberTheory.Primes -- from package arithmoi
-- "multiset" operations
pull :: Eq a => a -> [a] -> Maybe [a] pull x [] = Nothing pull x (y:ys) | x == y = Just ys pull x (y:ys) = pull x ys >>= \ys' -> return (y:ys')
union = (++) difference [] ys = [] difference (x:xs) ys = case pull x ys of Nothing -> x:(difference xs ys) Just ys' -> difference xs ys' intersection [] _ = [] intersection (x:xs) ys = case pull x ys of Nothing -> intersection xs ys Just ys' -> x:(intersection xs ys') subset xs ys = xs `intersection` ys == xs
expand :: Integer -> Integer -> [Integer] expand n b = reverse (expand' n) where expand' 0 = [] expand' n = (n `mod` b):(expand' (floor ((fromIntegral n) Prelude./ (fromIntegral b))))
contract :: [Integer] -> Integer -> Integer contract ds b = contract' ds ((length ds) - 1) where contract' [] _ = 0 contract' (d:ds) p = d * (b^p) + (contract' ds (p - 1))
rebase :: Integer -> Integer -> Integer -> Integer rebase = undefined
decompose :: Integer -> (Integer, Integer) decompose p = quotRem p 6
repeating :: Integer -> Integer -> Integer repeating n b = ((genericLength . takeWhile (== (head e))) e) - 1 where e = reverse (expand n b)
k n | n < 3 = [] k n = k' n (n - 2) where k' n 2 = let b = 2 ds = repeating n b in if ds > 0 then [(b, ds)] else [] k' n b = let ds = repeating n b in if ds > 0 then (b, ds):(k' n (b - 1)) else k' n (b - 1)
trailing b d n = e' !! 0 == d && e' !! 1 == d where e' = (reverse . (flip expand) b) n
-- the trivial dubs decision procedure - it computes its digit expansion dubs b n = e' !! 0 == e' !! 1 where e' = (reverse . (flip expand) b) n
-- base 2
{- the set of dubs in base two is exactly the set that contains 3, those numbers which contain {2, 2} in their prime factorization, and those numbers which contain {2, 2} in their prime factorization when you substract 3 from them -} dubs2_c' 3 = True dubs2_c' n = [2, 2] `subset` (factorize n) || [2, 2] `subset` (factorize (n - 3))
-- for some digit d and base b, contract [d, d] b = d * (b + 1)
atomic b n 0 = False -- 0 is not dubs atomic b n k = n - (k * (b + 1)) == 0 || atomic b n (k - 1)
-- an alternate dubs decision procedure dubs' b n = atomic b n (b - 1) || dubs'' b n (b - 1) where dubs'' b n 0 = ds `subset` (factorize n) dubs'' b n k = ds `subset` (factorize (n - (k * (b + 1)))) || dubs'' b n (k - 1) ds = (factorize b) `union` (factorize b)
-- base 10
zeros n = floor (fromIntegral ((length (filter (\p -> p == 2 || p == 5) (factorize n))) `div` 2))