丑数计算

要求输入一个n数输出第n个丑数。丑数是素因子只有2,3,5,7…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
package cal

import (
	"math"
	"sort"
)

// Ugly 丑数，基础
// base 素数数组 可以是 2,3,5|3,5,7
type Ugly struct {
	base  []int   // 基础素因子
	bmul  int     // 基础素因子 乘积
	cbase [][]int // 素因子对应的第i次计算次数
	ranks [][]int // 素因子各次值排序
}

// NewUgly 创建一个丑数计算基础
func NewUgly(base []int) *Ugly {
	sort.Ints(base)
	u := &Ugly{
		base: base,
		bmul: mul(base),
	}
	u.calNext()
	return u
}

// Get 获取第n个丑数
func (u *Ugly) Get(n int) int {
	for sumLen(u.ranks) < n {
		u.calNext()
	}
	sl := 0
	ret := 0
	for i := range u.ranks {
		li := len(u.ranks[i])
		if sl+li >= n {
			ret = u.ranks[i][n-sl-1]
			break
		}
		sl += li
	}
	return ret
}

// 第n次计算
func (u *Ugly) calNext() {
	var n = len(u.cbase) + 1
	var bb = make([]int, len(u.base))
	for i, b := range u.base {
		bb[i] = maxc(pow(u.bmul, n), b)
	}
	u.cbase = append(u.cbase, bb)
	//
	bn := make([]int, len(bb))
	var rank []int
	min := pow(u.bmul, n-1)
	for autoAdd(bn, bb) {
		pm := powmul(u.base, bn)
		if pm > min && pm <= pow(u.bmul, n) {
			rank = append(rank, pm)
		}
	}
	sort.Ints(rank)
	u.ranks = append(u.ranks, rank)
}

// 多元排序自增
// 返回是否还有下一个
// ln下限
func autoAdd(bn, ln []int) bool {
	if bn[0] < ln[0] {
		bn[0]++
		return true
	}
	bn[0] = 0
	if len(bn) == 1 {
		return false
	}
	return autoAdd(bn[1:], ln[1:])
}

// 获取a以b为底的整数部分
func maxc(a, b int) int {
	return int(math.Log(float64(a)) / math.Log(float64(b)))
}

// 获取乘积
func mul(nums []int) int {
	ret := 1
	for _, n := range nums {
		ret *= n
	}
	return ret
}

// 获取数组所有长度
func sumLen(a [][]int) int {
	l := 0
	for _, aa := range a {
		l += len(aa)
	}
	return l
}

func pow(x, n int) int {
	if n == 0 {
		return 1
	}
	ret := 1
	for i := 0; i < n; i++ {
		ret *= x
	}
	return ret
}

func powmul(a, b []int) int {
	var c = make([]int, len(a))
	for i := range a {
		c[i] = pow(a[i], b[i])
	}
	return mul(c)
}
测试代码
1
2
3
4
5
6
7
 
func TestUgly(t *testing.T) {
    ug := NewUgly([]int{2, 3, 5})
    n := ug.Get(1500)
    t.Log(n)
    t.Log(sumLen(ug.ranks))
    // t.Log(ug.ranks)
}
返回结果,与网上一些博客给出的答案859963392有差距1个index，本人是以2作为第一个丑数的
1
2
3
4
5
6
7
 
go test -v -run 'TestUgly'
=== RUN   TestUgly
--- PASS: TestUgly (0.00s)
    cal_test.go:32: 860934420
    cal_test.go:33: 2254
PASS
ok  	github.com/ipiao/metools/math/cal	0.006s
附上目标丑数附近的丑数序列
1
2
3
 
810000000 816293376 819200000 820125000 829440000 838860800 839808000 843750000
849346560 850305600 854296875 859963392 860934420 864000000 874800000 878906250
884736000 885735000 895795200 900000000 905969664 906992640 911250000